Algoritmos: búsqueda
Qué haremos
- Un algoritmo es una lista clara de pasos que resuelve un problema.
- Un trabajo muy común es la búsqueda: encontrar dónde está un valor en una lista.
- Aprenderemos dos algoritmos: búsqueda lineal y búsqueda binaria.
Búsqueda lineal
- Revisar los elementos uno por uno, desde el principio hasta el final.
- Si encuentras el valor, devuelve su índice (posición).
- Si llegas al final y nunca lo encuentras, devuelve
-1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))
Por qué ayuda una lista ordenada
- La búsqueda lineal funciona en cualquier lista, incluso una desordenada.
- Pero si la lista está ordenada (de menor a mayor), podemos ser mucho más rápidos.
- La búsqueda binaria usa el orden para saltarse la mitad de la lista cada vez.
Búsqueda binaria
- Mira el elemento del medio.
- Si es el objetivo, has terminado.
- Si el objetivo es menor, busca en la mitad izquierda; si es mayor, en la mitad derecha. Repite.
def binary_search(sorted_lst, target):
low = 0
high = len(sorted_lst) - 1
while low <= high:
mid = (low + high) // 2
if sorted_lst[mid] == target:
return mid
elif sorted_lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([1, 3, 5, 7, 9], 4))
Juntando ideas
- Una búsqueda combina tres bloques de construcción que ya conoces.
- Secuenciación: hacer pasos en orden. Selección:
if/elif/else. - Iteración: un bucle (
forowhile) repite la comprobación.
Pseudocódigo AP CSP
- El examen escribe un bucle y una comprobación así.
FOR EACHvisita cada elemento;IFselecciona;REPEAT UNTILrepite hasta que una prueba sea verdadera.
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
Errores comunes
- La búsqueda binaria necesita una lista ordenada.
- La búsqueda lineal revisa cada elemento a su vez.
Ahora tú prueban
- Cada tarea da un nombre de procedimiento y lo que debe devolver.
- Pulsa Check answer para probar tu código.
Búsqueda en una lista
La búsqueda binaria necesita una lista ordenada, pero es mucho más rápida que la lineal.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Escribe linear_search(lst, target). Devuelve el índice de target en lst, 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(sorted_lst, target) para una lista ordenada de menor a mayor. Devuelve el índice de target, o -1. Mira el elemento del medio y reduce la búsqueda a la mitad cada vez.
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 contains(lst, target) que devuelva True si target está en lst, de lo contrario False. Puedes reutilizar la búsqueda lineal y comparar el resultado con -1.
Haz clic en Ejecutar para ver la salida aquí.