Búsqueda: lineal y binaria
Encontrar un valor
- Un trabajo común es buscar: ¿hay un valor en un array y, ¿dónde está?
- La respuesta habitual es el índice donde se encontró, o
-1si no está. - Aprendemos dos formas: búsqueda lineal (funciona con cualquier array) y búsqueda binaria (necesita un array ordenado, pero es mucho más rápida).
Búsqueda lineal
- Revisa cada elemento desde el índice
0hacia el final. - Si el elemento es igual al objetivo, devuelve su índice de inmediato.
- Si el bucle termina sin encontrar coincidencia, devuelve
-1.
public class Main {
public static void main(String[] args) {
int[] a = {4, 8, 15, 16, 23};
int target = 15;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop early, we have it
}
}
System.out.println(found); // 2
}
}
¿Qué tan rápido es la búsqueda lineal?
- En el peor caso (el valor está al final o no existe) revisa todos los elementos.
- Para una lista de
nelementos, puede requerir hastancomprobaciones. A esto lo llamamos tiempo lineal. - Para arrays pequeños esto es totalmente aceptable. Para arrays grandes y ordenados podemos hacer mejor.
La búsqueda binaria necesita un array ordenado
- La búsqueda binaria solo funciona cuando el array ya está ordenado (de menor a mayor).
- Revisa el elemento del medio, luego descarta la mitad del array en cada paso.
- Eso es mucho más rápido: un millón de elementos toma alrededor de 20 comprobaciones, no un millón.
La idea de la búsqueda binaria
- Mantén dos límites:
low(inicio) yhigh(final). - Mira el índice del medio
mid = (low + high) / 2. - Si
a[mid]es igual al objetivo, devuelvemid. - Si
a[mid]es demasiado pequeño, el objetivo debe estar a la derecha, así que ajustalow = mid + 1. - Si
a[mid]es demasiado grande, el objetivo debe estar a la izquierda, así que ajustahigh = mid - 1. - Detente cuando
lowsupere ahigh; entonces el valor no está, devuelve-1.
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38}; // sorted!
int target = 16;
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1; // go right
} else {
high = mid - 1; // go left
}
}
System.out.println(found); // 4
}
}
Cuando falta un valor
- Ambas búsquedas devuelven
-1cuando el objetivo no está en el array. - En la búsqueda binaria, el bucle termina cuando
low > high— los límites se han cruzado, por lo que no queda nada más donde buscar. - Siempre maneja el caso de
-1en el código que llame a una búsqueda.
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12}; // sorted
int target = 7; // not in the array
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println(found); // -1
}
}
Errores comunes
- La búsqueda binaria necesita un array ordenado.
- La búsqueda lineal es O(n); la binaria es O(log n).
Ahora tú prueban
- Cada tarea prellena la estructura de la clase: escribe tu código dentro de main, o completa el método mostrado.
- Use Verificar respuesta para compilar su código con las pruebas proporcionadas y ver los resultados. Mantenga las interfaces de clase y método mostradas en el inicializador.
- Tu código se compila y ejecuta en el servidor, por lo que incluso la primera ejecución es rápida.
Búsqueda lineal vs. búsqueda binaria
La búsqueda binaria reduce a la mitad el rango en cada paso — mucho menos comprobaciones.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Completa linearSearch(int[] a, int target). Devuelve el índice del primer elemento igual a target, o -1 si no está en el array. Revisa los elementos desde el índice 0 hacia arriba.
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 binarySearch(int[] a, int target) para un array ordenado. Usa los límites low/high y revisa el medio en cada paso. Devuelve el índice de target, o -1 si no se encuentra.
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 countOccurrences(int[] a, int target) que devuelva cuántas veces aparece target en a (una exploración lineal). Devuelve 0 si nunca aparece.
Haz clic en Ejecutar para ver la salida aquí.