Binary Search Explained and Implemented in Python

Understand binary serach

The whole idea behind binary search is that you can take advantage of having the list you search in ordered.

Binary search explained

Say, we need to search for 7 and we look at the element in the middle of the list.

Binary search explained

Then we can conclude, in this example, that 7 is not part of the right side of the list, as all numbers must be greater than 10. That is because the list is ordered.

Next we ask the in the middle of the left side of the list which is left unknown is 7 is there.

Binary search explained

As -9 is less than 7, we know that 7 cannot be before in the list and are left with the remaining element between -9 and 10.

Binary search explained

As -3 is less than 7, we know that if 7 is part of the list, then it must be to the right of -3. Also, we know it must be before 10 (our first comparison).

Binary search explained

Hence, it can only be in the last spot left. But as it is 8, we now know that 7 is not part of the list.

Why is that impressive?

Consider if the list was unsorted. Then you would have to look through the entire list to make sure 7 was not part of it.

Binary search explained

In terms of complexity that means if the list contains N element, it must make N comparisons to search of an element. That is O(N) time complexity.

The binary search on the other hand is way more efficient. For each comparison the algorithm can skip one half of the list. That is O(log(N)) time complexity.

The source code

def recursive_binary_search(my_list, element):
    return recursive_binary_search_internal(my_list, element, 0, len(my_list) - 1)


def recursive_binary_search_internal(my_list, element, low, high):
    if low > high:
        return False
    else:
        mid = (low + high)//2
        if my_list[mid] == element:
            return True
        else:
            if my_list[mid] > element:
                return recursive_binary_search_internal(my_list, element, low, mid - 1)
            else:
                return recursive_binary_search_internal(my_list, element, mid + 1, high)


def binary_search(my_list, element):
    low = 0
    high = len(my_list) - 1
    while low <= high:
        mid = (low + high)//2
        if my_list[mid] == element:
            return True
        else:
            if my_list[mid] > element:
                high = mid - 1
            else:
                low = mid + 1
    return False


def main():
    my_list = [-29, -16, -15, -9, -6, -3, 8, 10, 17, 19, 27, 47, 54, 56, 60]
    print(my_list)
    element = 56
    print("Binary Search:", binary_search(my_list, element), element)
    print("Recursive Binary Search:", recursive_binary_search(my_list, element), element)


if __name__ == "__main__":
    main()

There are two implementations of the binary search in the above example.

Want to learn how to sort a list?

For the insertion sort read this tutorial. For the merge sort read this tutorial.

Leave a Reply