Algoritmos de búsqueda
Introducido| English | Significado |
|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | búsqueda lineal |
| binary search/ˈbaɪnəri sɜːtʃ/ | búsqueda binaria |
Veinte preguntas por un millón de nombres
- Un directorio telefónico contiene un millón de nombres. Si los revisa uno a uno, se espera realizar medio millón de comparaciones antes de encontrar el que busca.
- Ábralo en la mitad, decida en qué mitad está el nombre y descarte la otra. Repita. Llega a cualquier nombre en veinte comparaciones.
- Medio millón frente a veinte no es un ahorro menor; es la diferencia entre un programa que funciona y uno que no se puede usar. Y cuesta una cosa: la lista debe estar ya ordenada.
- Esta lección trata sobre búsqueda lineal y búsqueda binaria, cómo funciona cada una y cómo elegirlas.
Búsqueda lineal
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
- Recorre desde el principio, comparando cada elemento con el objetivo, y se detiene cuando encuentra una coincidencia o llega al final.
- Funciona con cualquier lista, ordenada o no, y con cualquier estructura que pueda ser recorrida paso a paso.
- Peor caso: el objetivo está al final o no existe, por lo que se comparan los $n$ elementos, lo cual es $O(n)$. En promedio, aproximadamente la mitad.

Una a la vez, desde el principio
Una búsqueda lineal:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
La búsqueda lineal no necesita preparación y funciona con cualquier lista, como máximo O(n).
La búsqueda lineal es la mejor opción cuando los datos están:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Sin un orden que aprovechar (o con una lista muy pequeña), la búsqueda lineal evita el costo de ordenar primero.
Búsqueda binaria
low ← 1 ; high ← n
WHILE low <= high DO
MiddleIndex ← (low + high) DIV 2
IF A[MiddleIndex] = target THEN
RETURN MiddleIndex
ENDIF
IF A[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE high ← MiddleIndex - 1
ENDWHILE
RETURN -1
- Requiere que los datos estén ordenados. Compare el elemento central con el objetivo: si coincide, deténgase; si el objetivo es mayor, descarte la mitad inferior; de lo contrario, descarte la mitad superior.
- Cada comparación reduzca a la mitad el rango que queda por buscar, por lo que el número de comparaciones es $O(\log_2 n)$.
- Por eso un millón de elementos necesitan unas veinte comparaciones: $2^{20}$ es apenas más de un millón.
Algoritmos de búsqueda
la búsqueda binaria reduce a la mitad el rango en cada paso
Lineal revisa cada elemento; binaria divide a la mitad una lista ordenada — mucho menos comparaciones.
La complejidad temporal en el peor caso de la búsqueda binaria es:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Reducir a la mitad el rango en cada paso da un número logarítmico de comparaciones.
¿Aproximadamente cuántas comparaciones necesita una búsqueda binaria para un millón de elementos ordenados?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
$\log_2(1\,000\,000) \approx 20$ — unas 20 comparaciones.
La búsqueda binaria se puede usar en cualquier lista, ordenada o no.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Decide qué mitad descartar comparando con el elemento central, lo cual solo tiene sentido si los datos están en orden.
La búsqueda binaria es $O(\log n)$ porque cada comparación ____ el rango restante por buscar.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Veinte mitades llevan un millón hasta uno, por eso $2^{20}$ siendo apenas superior a un millón es el número que se debe recordar.
Ejemplo resuelto: rastrear una búsqueda binaria
- La lista ordenada es 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Rastree la búsqueda del valor 23.
lowes 1,highes 10, por lo tantomides 5, que contiene 16. 16 es menor que 23, así que se descarta la mitad inferior:lowse convierte en 6.low6,high10, por lo tantomides 8, que contiene 56. 56 es mayor que 23, así quehighse convierte en 7.low6,high7, por lo tantomides 6, que contiene 23. Encontrado, en tres comparaciones donde una búsqueda lineal habría requerido seis.- Muestre
low,high,midy el valor en cada paso. La mayoría de los puntos están en el rastreo, no en la respuesta final.
En la lista ordenada 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, ¿cuántas comparaciones necesita una búsqueda binaria para encontrar 23?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
el medio 5 contiene 16 (demasiado pequeño), el medio 8 contiene 56 (demasiado grande), el medio 6 contiene 23. Una búsqueda lineal habría tardado seis.
Elegir entre ellos
| Lineal | Binaria | |
|---|---|---|
| Los datos deben estar ordenados | no | sí |
| Comparaciones, peor caso | $n$ | $\log_2 n$ |
| un millón de elementos | hasta 1,000,000 | aproximadamente 20 |
| Se adapta a | listas desordenadas o pequeñas, listas enlazadas | arreglos grandes ordenados, buscados repetidamente |
- Ordenar primero cuesta más que una búsqueda lineal, por lo que la búsqueda binaria solo compensa cuando la lista ya está ordenada o será buscada muchas veces.
- La búsqueda binaria también necesita acceso directo al elemento central, algo que tiene un arreglo pero no una lista enlazada.
Ejemplo resuelto: justificar la elección
- Un programa busca una lista desordenada de 50 registros una sola vez. Búsqueda lineal: ordenar la lista primero costaría mucho más que las 50 comparaciones que necesita la búsqueda.
- Un programa busca en un array ordenado de un millón de registros miles de veces por segundo. Búsqueda binaria: los datos ya están ordenados y cada búsqueda cuesta aproximadamente 20 comparaciones en lugar de hasta un millón.
- Un programa busca en una lista enlazada. Búsqueda lineal: la búsqueda binaria necesita saltar directamente al elemento central, y una lista enlazada solo se puede recorrer desde el principio.
- Nombre el algoritmo, luego la propiedad de los datos que lo decide.
Empareja cada búsqueda con sus hechos clave.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
La búsqueda binaria es mucho más rápida (O(log n)) pero solo sobre datos ordenados; la lineal funciona en cualquier lugar a O(n).
¿Cuándo es la búsqueda lineal la mejor opción? Selecciona todas las que correspondan.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
El último caso es exactamente donde gana la búsqueda binaria. Ordenar primero cuesta más que una única búsqueda lineal, así que solo compensa tras muchas búsquedas.
El costo de mantener el archivo ordenado
- La búsqueda binaria solo está disponible en una lista ordenada, y ese ordenamiento no es gratis. Una pregunta que le pide justificar una elección le está pidiendo que calcule su costo.
- Si los datos se buscan frecuentemente y cambian rara vez, ordénelos una vez y cada búsqueda posterior será $\log_2 n$. Ese es el caso de un diccionario o una tabla de consulta.
- Si los datos cambian constantemente, cada inserción debe mantener el orden, lo cual cuesta un desplazamiento de los elementos posteriores. Entonces, una búsqueda lineal sobre datos desordenados puede tener un costo total menor.
- Los números hacen concreto el argumento: un millón de registros necesitan hasta un millón de comparaciones linealmente, pero solo 20 mediante búsqueda binaria, ya que $2^{20} > 10^6$.
- Por lo tanto, la respuesta marcada menciona ambas mitades: con qué frecuencia se busca y con qué frecuencia cambia.
Ordena la justificación para elegir un algoritmo de búsqueda.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Una pregunta de justificación busca el compromiso, no el ganador. La búsqueda binaria en una lista que cambia constantemente puede costar más en total que una búsqueda lineal.
Puntos que se pierden fácilmente
- La búsqueda binaria requiere datos ordenados. Decir "es más rápida" sin esa condición hace perder puntos.
- Cada paso reduce a la mitad el rango, de ahí proviene el $\log_2 n$. Dé la razón, no solo la notación.
- Ambas búsquedas deben poder informar "no encontrado", para lo cual sirven el
-1y la condición del bucle. - La búsqueda binaria necesita acceso directo, por lo que no aplica a una lista enlazada incluso si la lista está ordenada.
Lo has entendido
- búsqueda lineal compara cada elemento desde el inicio, funciona con cualquier lista, y es $O(n)$
- La búsqueda binaria necesita datos ordenados con acceso directo, compara el medio y reduce a la mitad el rango cada vez, dando $O(\log_2 n)$: aproximadamente 20 comparaciones para un millón de elementos
- rastree una búsqueda binaria mostrando
low,high,midy el valor en cada paso - elija según los datos: desordenado, pequeño o lista enlazada significa lineal; grande, ordenado y buscado frecuentemente significa binario