Binary Search was one of the first algorithms I learned. It’s widely used in real-world scenarios and questions about it appear quite often during junior job interviews. I love its simplicity, intuitiveness and power. In this article I’ll do my best to take you by hand straight into the beautiful world of algorithmic thinking.

Overview

One of the most common tasks you will perform on a list is searching for a specific element. The simplest approach is to just go through every item, one by one, using “for loop” and compare it with a value you’re looking for. This procedure is called Linear Search and, as you imagine, it can get extremely slow with millions of elements. Luckily, if list is already sorted (which is often the case) we can use that to our advantage by applying Binary Search (yes, this search algorithm can be used only on sorted lists).

Problem

Find index of a given value in a sorted list of elements.

Steps

1. Find the middle of a list with given search bounds (index where search starts and index where search ends - at the first iteration these two variables should span through entire length of the list) and check if value you’re looking for is there.
2. If your value is in the middle, then congratulations - you found it. Algorithm completes. Otherwise there are two options:

Option A:

3. If your value is not in the middle and it’s greater than the middle element, then reject first half of the list - there is no point in searching there, since the list is sorted and all values below the middle are lesser than the one you’re looking for. You do this by updating the index at which the search starts (search_start_index).
4. Repeat from point 1. Remember that now there are new search bounds (you’ve just updated search_start_index to the current middle index + 1).

Option B:

3. If your value is not in the middle and it’s lesser than the middle element, then reject second half of the list - there is no point in searching there, since the list is sorted and all values above the middle are greater than the one you’re looking for. You do this by updating the index at which the search ends (search_end_index).
4. Repeat from point 1. Remember that now there are new search bounds (you’ve just updated search_end_index to the current middle index - 1).

5. Finish when the value is found in the middle or when start search bound is greater than end search bound (indicating that no element was found).

Visualization

Implementation in Python

def binary_search(list_to_search, search_start_index, search_end_index, search_item):
    # We will run this algorithm until start search bound is greater than end search bound.
    while search_start_index <= search_end_index:
        # Here we calculate the middle index of list given start and end bounds.
        middle_of_list = search_start_index + (search_end_index - search_start_index) // 2

        # If your value is in the middle, then congratulations - you found it. Algorithm completes.
        if list_to_search[middle_of_list] == search_item:
            return middle_of_list
        # If your value is not in the middle and it’s greater than the middle element, then reject first half of the
        # list - there is no point in searching there, since the list is sorted and all values below the middle are
        # lesser than the one you’re looking for. You do this by updating the index at which the search starts
        # (search_start_index).
        elif list_to_search[middle_of_list] < search_item:
            search_start_index = middle_of_list + 1
        # If your value is not in the middle and it’s lesser than the middle element, then reject second half of the
        # list - there is no point in searching there, since the list is sorted and all values above the middle are
        # greater than the one you’re looking for. You do this by updating the index at which the search ends
        # (search_end_index).
        else:
            search_end_index = middle_of_list - 1

    # If algorithm does not return in "while" loop then there is no search_item in the list, so return None
    return None


test_list = [17, 30, 31, 40, 48, 54, 58, 60, 70, 71]
result = binary_search(list_to_search=test_list,
                       search_start_index=0,
                       search_end_index=len(test_list) - 1,
                       search_item=70)

if result is not None:
    print(f"The item you're looking for is at index {result}.")
else:
    print("The item you're looking for is not in the given list.")