Algoritmos de búsqueda
Introducido| English | Significado |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | Búsqueda |
| linear search/ˈlɪnɪə sɜːtʃ/ | búsqueda lineal |
| binary search/ˈbaɪnəri sɜːtʃ/ | búsqueda binaria |
| sorted/ˈsɔːtɪd/ | ordenado |
Encontrar un valor
- Buscar significa localizar un valor objetivo en una colección.
- Dos algoritmos estándar: búsqueda lineal y búsqueda binaria.
- Ambos devuelven el índice donde se encuentra el objetivo — o una señal de "no encontrado" (a menudo
-1). - Cuál usar depende de si los datos están ordenados.
Búsqueda lineal
- Revisa cada elemento desde el inicio, uno por uno, hasta encontrar el objetivo.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- Funciona con cualquier array — ordenado o no.
- Peor caso: revisa todos los elementos (
ncomprobaciones).

La búsqueda lineal revisa cada elemento sucesivamente hasta encontrar el objetivo

La búsqueda binaria reduce la mitad del rango en cada paso
Búsqueda binaria
- Requiere una matriz ordenada. Observe el elemento central cada vez.
- Si el medio es el objetivo, terminó. Si el objetivo es más pequeño, busca en la mitad izquierda; si es más grande, en la mitad derecha.
- Cada paso reduz a la mitad el rango que queda por buscar.
- Mucho más rápido en arrays grandes ordenados: unas
log₂ ncomprobaciones, non.
Por qué la búsqueda binaria es rápida
- Búsqueda lineal de un millón de elementos: hasta un millón de comprobaciones.
- Búsqueda binaria de un millón de elementos ordenados: unas 20 comprobaciones.
- El requisito: el array debe estar ya ordenado.
- Reducir a la mitad repetidamente es la idea clave detrás de
O(log n).
La búsqueda binaria solo funciona en un array ORDENADO — ejecutarla sobre datos desordenados da respuestas incorrectas. También compara con el medio y descarta la mitad del rango en cada paso; una búsqueda lineal compara desde el inicio y elimina solo un elemento. Si no estás seguro de que los datos estén ordenados, debes usar búsqueda lineal (o ordenarlos primero).
Búsqueda binaria para el 7 en [1, 3, 5, 7, 9]:
- El medio es
5(índice 2). Como 7 > 5, busca en la mitad derecha. - La mitad derecha es
[7, 9]; el medio es7. Encontrado en el índice 3. - Dos comprobaciones en lugar de cuatro — el rango se redujo a la mitad cada vez.
Búsqueda lineal revisa elementos desde el inicio (funciona en cualquier array, hasta n comprobaciones). Búsqueda binaria necesita un array ordenado, compara con el medio y reduce a la mitad el rango de búsqueda en cada paso (unas log₂ n comprobaciones). Ambos devuelven el índice encontrado, o una señal de "no encontrado" como -1.
Búsqueda lineal vs binaria
La búsqueda binaria reduce a la mitad el rango ordenado en cada paso.
Una búsqueda lineal...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Lineal = de principio a fin; funciona con cualquier array.
La búsqueda binaria requiere que el array esté...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
La búsqueda binaria solo funciona con datos ordenados.
Cada paso de la búsqueda binaria...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Compara con el medio y mantiene una mitad.
Búsqueda binaria en [1,3,5,7,9] para 7: ¿cuántas comparaciones (mitad cada vez)?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Comparar con 5, luego con 7 — dos comparaciones.
La búsqueda binaria da resultados correctos en un array NO ORDENADO.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Depende del orden; los datos desordenados la rompen.
Empareja cada búsqueda con su propiedad.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
La lineal es general pero más lenta; la binaria es rápida pero necesita orden.