Table of Contents
To search the element x through binary search, we need a sorted array list.
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!")
Approach 2: Recursive
In the above python program, below steps are followed for Binary Search:
- Divide the sorted list into two equal half’s and compare the middle element with the x (search element).
- If x equalled to middle element of list, the value is returned.
- 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.
- Else if x is less than the middle element, the left half is treated as the list and steps 1 to 4 is followed.
- If the searched element is found, the value True is returned else False is returned.