Binary Search is a method of searching an element in a sorted list of items. It follows the divide and conquer approach. The list is divided into two halves. The key(element to be searched) is compared with the middle element of list. If the element is found the index is returned, else, the element is searched in either of the sub-list until found or the last sub-list(only one element remaining) is visited.
Illustration:
Algorithm
1. Initialize the sorted list, set low=0 and high=length(list)-1
2. Set mid=low+(high-low)//2
3. Compare key with element at mid
4. If list[mid]==key, then return mid
5. Else if list[mid]>key, then low=low and high=mid-1
6. Repeat from 2 till list[mid]=key, else return= -1
7. Else low=mid+1 and high=high
8. Repeat from 2 till list[mid]=key, else return=-1
9. If return = -1, then print "Not found"
End
Time Complexity:
- Worst Case: O(log n)
- Average Case: O(log n)
- Best Case: O(1)
Space Complexity: O(1)
Program for Binary Search
def binarySearch (li, low, high, x): # Returns index of element in li if present, else -1
if high >= low:
mid = low + (high - low) // 2
if li[mid] == x: #if element is present at mid
return mid
elif li[mid] > x: #If element is smaller than element at mid
return binarySearch(li, low, mid-1, x) # Element can only be present in left sub part of the li
else:
return binarySearch(li, mid + 1, high, x) #Else the element can only be present in right sub part of the li
else:
return -1 #Element not present in li
inp=input("Enter a sorted list: ").split()
li=[]
for i in inp:
li.append(int(i))
x = int(input("Element to be Searched: "))
# Function call
result = binarySearch(li, 0, len(li)-1, x)
if result != -1:
print ("Element is present at index % d" % result)
else:
print ("Element is not present in the list")