Binary search algorithm

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:

1. Use low and high to control which part of the list is searched

2. As long as the search area has not been narrowed down to one element, we select the middle element

3. Element found

4. Our guess is too big

5. Our guess is too low

6. 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