Searching · ⁨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 -1 si no se encuentra.
• Dos métodos clásicos son la búsqueda lineal y la búsqueda binaria.

Búsqueda lineal

• Revisa cada elemento por orden, comenzando desde el principio.
• Detente en cuanto encuentres 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.
• Mira el elemento del medio. Si es el objetivo, detente.
• Si el objetivo es menor, busca en la mitad izquierda; si es mayor, busca 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)

Compararlas

• La búsqueda lineal puede revisar cada elemento — 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: DIV es división entera (el equivalente a // en Python).

// Linear search — stop at the first match
found ← -1
i ← 0
WHILE i < LENGTH(list) AND found = -1
    IF list[i] = target THEN
        found ← i
    ENDIF
    i ← i + 1
ENDWHILE

// Binary search (list must be sorted)
found ← -1
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high AND found = -1
    mid ← (low + high) DIV 2
    IF list[mid] = target THEN
        found ← mid
    ELSE
        IF list[mid] < target THEN
            low ← mid + 1
        ELSE
            high ← mid - 1
        ENDIF
    ENDIF
ENDWHILE

Errores comunes

• La búsqueda binaria necesita una lista ordenada; reduce el rango a la mitad en cada paso.
• La búsqueda lineal funciona con cualquier lista, pero es más lenta.

Ahora tú intentas

• Devuelve el índice del valor, o -1 cuando no se encuentre.
• Pulsa Comprobar respuesta para probar tu código.