¿En qué casos se implementa el algoritmo de la búsqueda binaria? y ¿Porqué es más rápido que la búsqueda lineal?

@ImEngineerDew Para comprender por qué un algoritmo es mejor que otro utilizamos la teoría de complejidad algorítmica.

La aplicación del algoritmo de búsqueda binaria se puede dar cuando tenemos una colección de datos ordena (Puede ser cualquier tipo de colección).

Se dice que la búsqueda binaria es más rápida por que esta tiene una complejidad logarítmica binaria (base 2) en función de los elementos de la colección o O(log n), es decir, irá reduciendo a la mitad el problema por cada iteración que realice. Mientras que en la búsqueda lineal, su complejidad es lineal o O(n), lo que quiere decir que esté algoritmo siempre tendrá que recorrer todos los elementos para saber si se encuentra lo que estamos buscando.

Ejemplo

En el siguiente algoritmo se plantea una lista de 10 productos ordenados por precio y se necesita buscar el producto con el precio "21.99", dónde a la búsqueda binaria le toma solo 4 pasos resolver el problema a la búsqueda lineal le toma 10 pasos (la cantidad de productos).

Resultado.

Código

# A list of products ordered by the price
products = [
    {'id': 1, 'name': 'Product #1', 'price': 2.49},
    {'id': 2, 'name': 'Product #2', 'price': 2.99},
    {'id': 3, 'name': 'Product #3', 'price': 3.5},
    {'id': 4, 'name': 'Product #4', 'price': 3.5},
    {'id': 5, 'name': "Product #5", 'price': 4.25},
    {'id': 6, 'name': 'Product #6', 'price': 4.99},
    {'id': 7, 'name': 'Product #7', 'price': 6.5},
    {'id': 8, 'name': 'Product #8', 'price': 6.99},
    {'id': 9, 'name': 'Product #9', 'price': 7.99},
    {'id': 10, 'name': 'Product #10', 'price': 21.99}
]


def binary_search(list, item, step_config):
    """Searches for a product in the list by its price using the binary search algorithm.

    Time complexity: O(log(n))
    """

    low = 0
    high = len(list) - 1

    while low <= high:
        step_config['binary'] += 1

        mid = (low + high) // 2
        guess = list[mid]["price"]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None


def linear_search(list, item, steps_config):
    """Searches for a product in the list by its price using the linear search algorithm.

    Time complexity: O(n)
    """

    for idx, product in enumerate(list):
        steps_config['linear'] += 1

        if product["price"] == item:
            return idx

    return None


if __name__ == '__main__':
    steps = {
        'binary': 0,
        'linear': 0
    }
    # Search for the product with the price of 21.99 using binary search
    matches = binary_search(products, 21.99, steps)

    # Print the product
    if matches is not None:
        print(products[matches])
    else:
        print("No matches found using binary search")

    # Search for the product with the price of 21.99 using linear search
    matches = linear_search(products, 21.99, steps)

    # Print the product
    if matches is not None:
        print(products[matches])
    else:
        print("No matches found using linear search")

    # Print the number of steps taken by the binary search algorithm
    print("Binary search steps: " + str(steps['binary']))

    # Print the number of steps taken by the linear search algorithm
    print("Linear search steps: " + str(steps['linear']))