This is a short post to share python implementation of binary search. What’s binary search you ask? It’s simple.
Imagine you have a list of numbers and you want to check if a particular number exists in it. Normally you’d search it one by one. That’s fine and this approach is called linear search.
The problem with linear search is that if the list of numbers is 1 million, it will take 1 million checks before we can confidently say whether the number exists in it or it doesn’t.
That’s where binary search is helpful. But in order for binary search to work, the list must be sorted.
In binary search, you look at the middle element of a sorted list and see if it is equal to the number we are looking for. If it isn’t, we only look at the first half of the list or the second half. Reducing the list in half at each check.
Thus, if the length of the list is N, binary search will take O(log N) time whereas linear search takes O(N).
Here’s python implementation of binary search:
def binary_search(arr, item):
l = 0
r = len(arr)-1
while l<=r:
mid = l + (r-l)//2
if item == arr[mid]:
return True
elif item < arr[mid]:
r = mid-1
else:
l = mid+1
return False
#testing
arr = [2,5,6,9,11,15,18,20]
print(binary_search(arr, 1)) # prints False
print(binary_search(arr, 21)) # prints False
print(binary_search(arr, 20)) # prints True
print(binary_search(arr, 2)) # prints True
print(binary_search(arr, 11)) # prints True
Highlighted lines are really important to remember. We usually make mistakes there. For example, forgetting to return False if we don’t find the item in the given list.
Also, the explanation for mid = r - (r-l)//2 can be found here in a Stack Overflow post which is funny because it is an overflow related issue. This is also addressed in a Google blog here.
CS Mumbai 