Binary search is an algorithm in which a sorted list of elements is given as input. If the list contains the item we are looking for, the algorithm returns information about its location. Otherwise, it returns the null value.
In a binary search, we guess the middle number in order to eliminate half of the remaining numbers in each trial.
def binnary_search(list, item): low = 0 high = len(list) - 1 #1 while low <= high: mid = round(low + high) // 2 #2 guess = list[mid] if guess == item: #3 return mid if guess > item: #4 high = mid - 1 else: #5 low = mid + 1 return None my_list = [1, 2, 3, 5, 7, 9, 11, 23, 123, 345] print(binnary_search(my_list, 345)) #9 print(binnary_search(my_list, 11)) #6 print(binnary_search(my_list, 15)) #None
Let's break this program down into parts:
Use low and high to control which part of the list is searched
As long as the search area has not been narrowed down to one element, we select the middle element
Our guess is too big
Our guess is too low
There is no such element
Remember that numbering in lists starts at 0
Binary search is a good alternative to searching the entire list of items one by one. The speed of a binary search with a list of 10 elements is O(log 10) which gives us a maximum of 4 guesses.
More about Big O notation you can read in my previous post here