Algorithms: searching · Algoritmos: búsqueda
What we'll do
- An algorithm is a clear list of steps that solves a problem.
- A very common job is searching: find where a value is in a list.
- We will learn two algorithms: linear search and binary search.
Lo que 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.
Linear search
- Check the items one by one, from start to end.
- If you find the value, return its index (position).
- If you reach the end and never find it, return
-1.
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))
Why a sorted list helps
- Linear search works on any list, even a messy one.
- But if the list is sorted (small to big), we can be much faster.
- Binary search uses the sorted order to skip half the list each time.
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.
Binary search
- Look at the middle item.
- If it is the target, you are done.
- If the target is smaller, search the left half; if bigger, the right half. Repeat.
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))
Putting ideas together
- A search combines three building blocks you already know.
- Sequencing: do steps in order. Selection:
if/elif/else. - Iteration: a loop (
fororwhile) repeats the check.
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.
In AP CSP pseudocode
- The exam writes a loop and a check like this.
FOR EACHvisits every item;IFselects;REPEAT UNTILloops until a test is true.
En 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)
}
Common mistakes
- Binary search needs a sorted list.
- Linear search checks each item in turn.
Errores comunes
- La búsqueda binaria necesita una lista ordenada.
- La búsqueda lineal revisa cada elemento a su vez.
Now you try
- Each task gives a procedure name and what it must return.
- Press Check answer to test your code.
Ahora tú intentas
- Cada tarea da un nombre de procedimiento y lo que debe devolver.
- Presiona Check answer para probar tu código.
Searching a list · Búsqueda en una lista
Binary search needs a sorted list but is far faster than linear. · La búsqueda binaria necesita una lista ordenada, pero es mucho más rápida que la lineal.
Write linear_search(lst, target). Return the index of target in · hacia adentro lst, or -1 if it is not there. Check items one by one. · Escribe linear_search(lst, target). Devuelve el índice de target en lst, o -1 si no está. Revisa los elementos uno por uno.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write binary_search(sorted_lst, target) for a list sorted small to big. Return the index of target, or -1. Look at the middle and cut the search in half each time. · 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.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Write contains(lst, target) that returns True if target is in lst, else False. You may reuse linear search and compare the result to -1. · 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.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.