El algoritmo de búsqueda binaria

En esta lección verás el algoritmo de búsqueda binaria, para entender cómo encontrar de forma eficiente un valor en datos ya ordenados. Está pensada para quien busca «búsqueda binaria en Python».

La búsqueda binaria es un algoritmo para encontrar eficientemente un valor en datos que ya están ordenados. Piénsalo como abrir un diccionario más o menos por la mitad e ir reduciendo el margen de búsqueda a la mitad cada vez. Comparada con revisar los elementos uno a uno desde el principio, encuentra el objetivo muchísimo más rápido cuantos más datos haya.

El código de ejemplo gestiona el rango de búsqueda con dos índices, low y high, comparando el valor central, mid, con target. // es el operador de «división entera» de Python, que redondea hacia abajo el resultado de una división. Si no encuentra nada, devuelve -1.

Un error habitual al empezar es olvidar el requisito de que los datos deben estar ya ordenados. Ejecutar una búsqueda binaria sobre una lista sin ordenar no da resultados correctos. Python también tiene una implementación rápida y específica en el módulo bisect, que en el trabajo real se usa a menudo en lugar de escribirla a mano.

Como tema fundamental de estructuras de datos y algoritmos, es también un clásico de las entrevistas técnicas y las pruebas de selección. En sistemas grandes con millones de registros, la ventaja de velocidad de la búsqueda binaria se vuelve especialmente relevante.