Algoritmo de búsqueda binaria de Python

Busque listas ordenadas en tiempo logarítmico O (log n). Ejecute y comprenda la búsqueda binaria en Python, incluida la lógica paso a paso, los casos extremos y las optimizaciones.

Pruébelo en el editor

Descripción general

La búsqueda binaria es un algoritmo excepcionalmente eficiente para encontrar un elemento en una lista ordenada. A diferencia de la búsqueda lineal, que escanea cada elemento secuencialmente en un tiempo O(n), la búsqueda binaria funciona dividiendo repetidamente el intervalo de búsqueda por la mitad.

La búsqueda comienza examinando el elemento central de la matriz. Si el valor objetivo coincide con el elemento central, se devuelve su posición. Si el objetivo es más pequeño, el algoritmo limita su búsqueda a la mitad inferior; si el objetivo es más grande, lo estrecha a la mitad superior. Este proceso se repite hasta que se encuentra el elemento o el tamaño del subarreglo cae a cero.

Para implementar la búsqueda binaria en Python, utilizamos dos punteros (bajo y alto) para rastrear los límites de búsqueda activos. Dado que el espacio de búsqueda se reduce a la mitad en cada paso, el algoritmo se ejecuta en un tiempo O(log n), lo que lo hace ideal para bases de datos masivas.

Código y salida de ejecución

Una implementación de búsqueda binaria iterativa estándar que devuelve el índice de un elemento de destino en una lista ordenada.

binary_search.py

Pruébelo en el editor

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23

index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
    print(f"Target found at index: {index}")
else:
    print("Target not found in dataset")

Salida terminal

Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5

Implementación paso a paso

Indexación de consultas y búsqueda en tablas de bases de datos.
Encontrar valores umbral o límite en rangos matemáticos continuos
Funciones de autocompletar y búsqueda en campos de texto

Preguntas frecuentes

¿Es necesario ordenar la lista para que funcione la búsqueda binaria?

Sí, la búsqueda binaria se basa estrictamente en los elementos que se ordenan. Si la lista no está ordenada, la lógica de comparación se rompe y primero debe ordenar la lista o utilizar una búsqueda lineal.

¿Por qué utilizar la búsqueda binaria iterativa en lugar de la búsqueda binaria recursiva?

Si bien la búsqueda binaria recursiva es elegante, en producción suele preferirse la búsqueda binaria iterativa. El enfoque iterativo se ejecuta en el espacio auxiliar O(1), mientras que la búsqueda recursiva ocupa el espacio O(log n) debido a la pila de llamadas, lo que corre el riesgo de que la pila se desborde en entradas extremadamente grandes.

Temas relacionados

Algoritmos de clasificación de Python

Explore los algoritmos de clasificación de Python. Visualice la clasificación por burbujas y la clasificación por combinación de forma nativa dentro del contexto IDE de un navegador.

Tutorial del algoritmo de ordenación y combinación de Python

Aprenda a implementar Merge Sort en Python. Un ejemplo interactivo paso a paso de la estrategia de clasificación Divide y vencerás.

Guía del algoritmo de clasificación rápida de Python

Explore el algoritmo de clasificación rápida en Python. Aprenda la selección dinámica, la partición y la recursividad en este ejemplo de codificación interactivo.