Binary Search

by

The second algorithm that I would like to introduce here is also a search algorithm, the binary search. The following example is about searching for a value in a list.

numbers = [4, 43, 12, 89, 17, 23, 1, 66, 103]

To use binary search, it is necessary to first sort this list. The sort() method can be used for this:

numbers.sort()
print(numbers)  # -> [1, 4, 12, 17, 23, 43, 66, 89, 103]

Next, you need to find the value that is in the middle of the list. Regarding the value we are looking for, there are three possibilities:

  1. The value you are looking for corresponds exactly to the value in the middle of the list.
  2. The item you are looking for is in the first half of the list.
  3. The item you are looking for is in the second half of the list.

If the value you are looking for is exactly the value in the middle of the list, then the search is finished. Otherwise, only the half in which the value must be located is searched. With each subsequent pass, another half of the list is excluded.

The code could look like this:

def binary_search(number_list, number):
    """A binary search function

    Arguments:
        number_list {list} -- A list with sorted integer values
        number {integer} -- The number we are searching for

    Returns:
        integer -- Returns the index of the given number
    """
    lower_bound = 0
    upper_bound = len(numbers)

    while lower_bound < upper_bound:
        mid_index = lower_bound + (upper_bound - lower_bound) / 2
        mid_index = int(mid_index)

        if number_list[mid_index] == number:
            return mid_index
        elif number_list[mid_index] < number:
            lower_bound = mid_index + 1
        else:
            upper_bound = mid_index

index_value = binary_search(numbers, 89)
print(index_value)  # -> Index 7

Time complexity of binary search

Ideally, the value you are looking for is the same as the value in the middle of the list. If this is not the case, the list is reduced by half each time the while loop is run. A binary search is therefore performed on half of the list with size at most n/2. In the next step, a list of size at most n/4 is searched. This means that with each pass the values ​​to be searched are reduced by a factor of two.

  • In the best case, the time complexity of a binary search is therefore O(1).
  • In the worst case, the time complexity of a binary search is therefore O(log n).