Búsqueda binaria en Python

La forma más rápida de buscar en datos ordenados — O(log n) le gana al escaneo.

def busqueda_binaria(elementos, objetivo):
    bajo, alto = 0, len(elementos) - 1
    while bajo <= alto:
        medio = (bajo + alto) // 2
        if elementos[medio] == objetivo:
            return medio
        if elementos[medio] < objetivo:
            bajo = medio + 1
        else:
            alto = medio - 1
    return -1

Cómo funciona

1. Mantiene los punteros bajo y alto alrededor de la región aún en juego.
2. Revisa el elemento del medio en cada pasada.
3. Parte el espacio de búsqueda a la mitad hasta hallar el objetivo o vaciar la región.

Palabras clave y builtins usados aquí

• def
• else
• if
• len
• return
• while

El intento, en números

Líneas

11

Caracteres a escribir

252

Tokens

69

Ritmo de tres estrellas

100 tpm

Al ritmo de tres estrellas de 100 tokens por minuto, este intento toma unos 41 segundos.

Escribe este fragmento

Paso 2 de 5 en Algoritmos; paso 52 de 72 en Fundamentos del lenguaje.

← Anterior Siguiente →