Significado y funcionamiento
La búsqueda lineal verifica los valores de forma secuencial, mientras que la búsqueda binaria examina el punto medio del rango actual. Si se sabe si el punto medio es menor o mayor que el valor objetivo, se puede descartar la mitad del rango utilizando el ordenamiento.
En las siguientes comparaciones, se mantiene la condición de que si existe una solución, ésta debe estar ubicada dentro del intervalo restante. Si un intervalo se vuelve vacío, concluimos que no existe ningún valor dentro de él.
Relaciones y condiciones de validez
El número de candidatos disminuye aproximadamente como n/2ᵏ, por lo que el número de comparaciones crece logarítmicamente. Para la lista sin duplicados de la simulación, con n≥1, el número máximo de comparaciones puede ser comparado con ⌊log₂n⌋ + 1.
El costo de ordenamiento debe considerarse por separado del costo de búsqueda. Cuando se aborda el problema de encontrar las primeras y últimas posiciones en una lista con valores duplicados, las condiciones de parada deben ajustarse.
Qué observar en la simulación
La búsqueda binaria reduce a la mitad el intervalo en cada paso.
La lista ordenada no tiene duplicados. Ambos métodos usan la misma lista.
Relaciones y símbolos clave
binary steps ≤ ⌊log₂n⌋ + 1
| Símbolo | Significado | Unidad |
|---|---|---|
| n | Número de datos | unidades |
| k | Número de comparaciones y reducciones del intervalo | ensayo |
Ejemplo resuelto
¿Qué requiere la búsqueda binaria?
Una lista ordenada · La búsqueda binaria reduce a la mitad el intervalo en cada paso.
Errores frecuentes
- Aplicar únicamente la regla de comparación de la mediana a una lista no ordenada no resulta en una búsqueda binaria correcta.