Búsqueda: lineal y binaria
Dos formas de buscar
- Buscar significa encontrar dónde se encuentra un valor en un array (o indicar que no está allí).
- Búsqueda lineal revisa cada elemento uno por uno. Funciona con cualquier array.
- Búsqueda binaria es mucho más rápida, pero requiere que el array esté ordenado primero.
Búsqueda lineal
- Recorre desde el índice
0hastan - 1, comparando cada elemento con el objetivo. - Devuelve el índice en el momento en que lo encuentres. Si llegas al final, devuelve
-1. - Para un array de
nelementos, esto examina hastande ellos.
Por qué el ordenamiento permite la búsqueda binaria
- Si el array está ordenado, puedes saltar a la mitad y comparar.
- Si el valor central es demasiado pequeño, el objetivo debe estar en la mitad derecha; si es demasiado grande, en la mitad izquierda.
- Cada paso descarta la mitad del array, por lo que es muy rápido (aproximadamente
log2(n)pasos).
low, high, mid
- Mantén dos límites:
low(inicio) yhigh(final). El punto medio esmid = low + (high - low) / 2. - Si
a[mid]es el objetivo, devuelvemid. Sia[mid] < target, muevelow = mid + 1; de lo contrario,high = mid - 1. - Detente cuando
low > high: el objetivo no está ahí, así que devuelve-1.
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
Errores comunes
- La búsqueda binaria necesita un array ordenado.
- La búsqueda lineal revisa cada elemento sucesivamente.
Ahora tú prueban
- Para la búsqueda binaria, asume que el array ya está ordenado. Usa
low,highymid. - Devuelve
-1cuando el valor no se encuentre. No escribas una funciónmain— el sistema de verificación proporciona una.
Búsqueda lineal vs. búsqueda binaria
La búsqueda binaria reduce a la mitad el rango en cada paso.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Completa int linear_search(const int a[], int n, int target) para que devuelva el índice del primer target, o -1 si no está en el array. No escribas un main.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Completa int binary_search(const int a[], int n, int target) para un array ordenado. Devuelve el índice de target, o -1. Usa low, high y mid. No escribas un main.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Completa int first_negative(const int a[], int n) para que devuelva el índice del primer elemento menor que 0, o -1 si no hay ninguno. No escribas un main.
Haz clic en Ejecutar para ver la salida aquí.