[Python] Binary Search

“human beings have a strong dramatic instinct toward binary thinking, a basic urge to divide things into two distinct groups, with nothing but an empty gap in between. We love to dichotomize. Good versus bad. Heroes versus villains. My country versus the rest. Dividing the world into two distinct sides is simple and intuitive, and also dramatic because it implies conflict, and we do it without thinking, all the time.”

― Hans Rosling, Factfulness: Ten Reasons We’re Wrong About the World – and Why Things Are Better Than You Think

Photo by Delia Giandeini on Unsplash

Consider the quite typical starting line-up for Juventus when Andrea Pirlo was the coach in the 2020/21 season:

Assume that we have a sorted list of players numbers as follows:

[3, 4, 7, 13, 14, 16, 22, 25, 28, 30, 44]

And we want to find out if a certain player is playing just by their kit number. For instance, we are looking for player with the shirt number 44. Here is how binary search works:

And we want to find out if a certain player is playing just by their kit number. For instance, we are looking for player with the shirt number 44. Here is how binary search works:

1. We find the element which stands on the middle index of this list
   
   
2. Check if this element is equal to the number we are looking for. If yes, then problem is solved, otherwise go to the next step. 
3. Check if the number we are looking for is higher or lower than this element. If the desired number is higher, then it should be located to the right of the current element and vice versa. 
4. Continue in this manner until we either find the number of we get sure that the number does not exist in this list. 
5. In our example, the middle index is  = 5 and the element at index 5 is 14. Because 14 < 44, it means that the kit number we are looking for must be to the right hand side of the current index. Therefore, we update our search region, and continue. More generally, if we denote the lower limit by a, the upper limit by b, and the index at the middle by c, then our search can be summarized as follows:

As it can be seen, the kit that we were looking for was found in four iterations. Bear in mind that the number that we were looking for, was the maximum in its array. If we wanted to look for it normally, starting from the left, it would have taken 11 moves (the length of the list) to be found.

This shows that binary search can increase the lookup speed quite significantly. In the best case scenario, the search would last for only one iteration, if the number we are looking for is exactly at the middle of the array. On the other hand, in the worst case scenario, if the number we are looking for is on either end of the list, like the example we just saw, then the algorithm keeps dividing the search range until the number is finally found. This means that the time complexity of binary search is O(log n), whereas the linear search has the time complexity of O(n).

It is important to note that the binary search only works if the array is sorted.

Let’s implement binary search algorithm in Python:

# Econowmics.com

# Function to find an element in a list using binary search algorithm
def binary_search(_list, num):
    '''Receives a list of numbers, and return the index of a desired number, 
     plus the amount of iterations it took to find this number'''
    
    # variable to keep count of total iterations
    iterations = 0
        
    # define the lower and upper limits
    lower, upper = 0, len(_list)-1
        
    # loop to find the number
    while True:     
        # find the middle index
        middle = (lower + upper) // 2
            
        # check if the element at this index is what we are looking for
        if _list[middle] == num:
            print ('The number', num, 'was found after', iterations+1, 'iterations at index', middle)
            break
        # Otherwise, we should narrow our search range  
        else:
            # if the number we are looking for is larger than the number at the middle
            # then what we are looking for is in the right half of the list
            if num > _list[middle]:
                lower = middle + 1 
            # otherwise, the number we are looking for is in the left half of the list
            else:
                upper = middle - 1
                    
        # update total iteration
        iterations += 1
        
        

Kit_nums = [3, 4, 7, 13, 14, 16, 22, 25, 28, 30, 44]
binary_search(Kit_nums, 44)
binary_search(Kit_nums, 16)

As a final step, we can try the function we just wrote on the list of numbers we defined at the beginning:

This will be the results: