Búsqueda
Buscar en una lista
- Buscar significa encontrar si un valor está en una lista y dónde se encuentra.
- La respuesta habitual es el índice del valor, o
-1si no existe. - Dos métodos clásicos son la búsqueda lineal y la búsqueda binaria.
Búsqueda lineal
- Revisar cada elemento por turno, desde el inicio.
- Detenerse tan pronto como se encuentre una coincidencia.
- Funciona con cualquier lista, ordenada o no.
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
Búsqueda binaria
- La búsqueda binaria necesita una lista ordenada.
- Observar el elemento del centro. Si es el objetivo, detenerse.
- Si el objetivo es menor, buscar en la mitad izquierda; si es mayor, en la mitad derecha.
data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
print(found)
Comparación
- La búsqueda lineal puede revisar todos los elementos — lenta para listas largas.
- La búsqueda binaria descarta la mitad de la lista en cada paso, por lo que es mucho más rápida.
- Pero la búsqueda binaria solo funciona si los datos ya están ordenados.
En pseudocódigo de Cambridge
- Nota:
DIVes división entera (Python's//). - Los arreglos de Cambridge generalmente se ejecutan desde 1 hasta
n, el número de elementos.LENGTH()es para cadenas, por lo que los bucles usann.
// Linear search — stop at the first match
found ← -1
i ← 1
WHILE i <= n AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 1
high ← n
WHILE low <= high AND found = -1
MiddleIndex ← (low + high) DIV 2
IF list[MiddleIndex] = target THEN
found ← MiddleIndex
ELSE
IF list[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
Errores comunes
- La búsqueda binaria necesita una lista ordenada; reduce a la mitad el rango en cada paso.
- La búsqueda lineal funciona con cualquier lista pero es más lenta.
Ahora tú prueban
- Devolver el índice del valor, o
-1cuando no se encuentra. - Pulsa Check answer para probar tu código.
Búsqueda lineal vs binaria
La búsqueda binaria reduce a la mitad la lista en cada paso — mucho menos comparaciones.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Escribe linear_search(items, target) que devuelva el índice de target en items, o -1 si no está. Revisa los elementos uno por uno.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Escribe binary_search(items, target) para una lista ordenada. Devuelve el índice de target, o -1 si falta. Reduce el rango a la mitad en cada paso.
Haz clic en Ejecutar para ver la salida aquí.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Escribe first_negative(items) que escanee la lista y devuelva el índice del primer número menor que 0, o -1 si no hay ninguno.
Haz clic en Ejecutar para ver la salida aquí.