Introduction

To search the element x through binary search, we need a sorted array list.

Program

Approach 1: Iterative

def search(ip_arr, x):
    l = 0
    h = len(ip_arr) - 1
    mid = 0
    while l <= h:
        mid = (h + l) // 2
        if ip_arr[mid] < x:
            l = mid + 1
        elif ip_arr[mid] > x:
            h = mid - 1
        else:
            return mid
    return -1
   
ip_arr = [101, 4, 98, 7]
x = 98
output = search(ip_arr, x)
if output != -1:
    print("The element is present at index", str(output))
else:
    print("The element is not present in the given array!")

Output

Approach 2: Recursive

Output:

Explanation

In the above python program, below steps are followed for Binary Search:

1. Divide the sorted list into two equal half’s and compare the middle element with the x (search element).
2. If x equalled to middle element of list, the value is returned.
3. Else if x is greater than the middle element, the right half is treated as the list and again step 1 to step 4 is followed.
4. Else if x is less than the middle element, the left half is treated as the list and steps 1 to 4 is followed.
5. If the searched element is found, the value True is returned else False is returned.