30. Binary search

The binary search algorithm is faster than the linear search algorithm studied in the previous unit.

This algorithm takes advantage of the fact that a list is already ordered to find the desired element more quickly. These are the steps of the algorithm:

1. Repeat everything as long as there is a list to search.
2. We look for the element in the middle of the list.
3. If the element is found, returns the position of the found element.
4. If the searched item is larger than the item in the middle of the list, we split the list in two and will only search the top half of the list.
5. In case the searched item is smaller than the item in the middle of the list, we split the list in two and will only search the bottom half of the list.
6. If the element was not found, returns None

Binary search example

This is an example of a list to search for an element, with the positions of the numbers:

lista = [
    8, 13, 17, 19, 33, 35, 40, 42, 44, 46, 51, 53, 63, 72, 75, 85, 87, 89, 92, 99 ]
#  ^  ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^
#  0  1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19

Let's search for element 89 in this list with binary search.

First we search in the middle of the list, position 9, which returns the number 46. Since 46 is less than 89, we know that the searched element can only be in the upper half of the list:

lista = [
    8, 13, 17, 19, 33, 35, 40, 42, 44, 46, 51, 53, 63, 72, 75, 85, 87, 89, 92, 99 ]
#                                         ^   ^   ^   ^   ^   ^   ^   ^   ^   ^
#                                         10  11  12  13  14  15  16  17  18  19

Now we search in the top half of the list, at position 14, which returns the number 75. Since 75 is less than 87, we know that the searched item could only be in the top half of the list:

lista = [
    8, 13, 17, 19, 33, 35, 40, 42, 44, 46, 51, 53, 63, 72, 75, 85, 87, 89, 92, 99 ]
#                                                             ^   ^   ^   ^   ^
#                                                             15  16  17  18  19

We search again in the middle of the upper part of the list, at position 17, which returns the number 89. This is the element searched for, so we can return position 17.

As we can see, with only 3 comparisons the searched element was found in position 17. A linear search would have required 18 comparisons in total.

Binary search is therefore much faster than linear search, especially on very large lists of elements, with the disadvantage that it needs to search a list that is already sorted.

Binary search program

The program to perform a binary search will have two indexes, start and end. One points to the beginning of the list and another to the end of the list. These indexes will be updated as we learn which part of the list may contain the searched element:

def busqueda_binaria(lista, buscado):
    inicio = 0
    final = len(lista) - 1

    while inicio <= final:
        medio = (inicio + final) // 2
        if lista[medio] == buscado:
            return medio
        elif lista[medio] < buscado:
            inicio = medio + 1
        else:
            final = medio - 1

    return None


lista = [
    8, 13, 17, 19, 33, 35, 40, 42, 44, 46,
    51, 53, 63, 72, 75, 85, 87, 89, 92, 99
    ]
buscado = 87

resultado = busqueda_binaria(lista, buscado)

if resultado == None:
    print(f'El elemento {buscado} no se encuentra en la lista')
else:
    print(f'El elemento {buscado} se encuentra en la posición {resultado}')

Exercises

1. Program a binary search function that returns the position at which a new element should be placed so that it is sorted within a list of already sorted numbers.

   Clue:

   def posicion_insertar(lista, nuevo_numero):
       inicio = 0
       final = len(lista) - 1
   
       while inicio <= final:
           ...
           ...
           ...
   
       return ...
   
   
   lista = [
       8, 13, 17, 19, 33, 35, 40, 42, 44, 46,
       51, 53, 63, 72, 75, 85, 87, 89, 92, 99
       ]
   
   nuevo_numero = 68
   posicion = posicion_insertar(lista, nuevo_numero)
   print(f'El número {nuevo_numero} debería insertarse en la posición {posicion}')
   

   Exit:

   El número 68 debería insertarse en la posición 13
   

   Try the program with the numbers 7, 25, 48 and 100.

   The correct results are positions 0, 4, 10 and 20.