Publicado · en mejora
Algorithm
Los algoritmos de búsqueda localizan valores o posiciones: búsqueda lineal y binaria, lower_bound y upper_bound, búsqueda sobre la respuesta y hashing.
Buscar consiste en encontrar un valor dentro de una colección de datos, o la posición en la que una condición se cumple por primera vez. La búsqueda lineal revisa los elementos uno a uno y sirve para cualquier dato, mientras que la búsqueda binaria divide a la mitad un rango ordenado en cada paso y solo necesita unas 20 comparaciones para un millón de elementos. Para coincidencias exactas, una tabla hash responde en tiempo constante en promedio.
La búsqueda es fundamental porque casi todos los programas consultan datos: los índices de bases de datos, el autocompletado, el análisis de registros y las tablas de enrutamiento dependen de ella. Además, la búsqueda binaria no se limita a los arreglos. Si una condición de sí o no cambia una sola vez a lo largo de un rango, se puede buscar binariamente la propia respuesta, lo que convierte muchos problemas de optimización de entrevistas técnicas en código breve y fiable.
Conviene empezar escribiendo una búsqueda lineal y una búsqueda binaria con intervalo cerrado, y luego practicar las formas lower_bound y upper_bound con intervalo semiabierto hasta que el manejo de los límites resulte natural. Sigue a mano la ejecución sobre arreglos pequeños, compara tu código con el módulo bisect de Python usando entradas aleatorias y, por último, practica la búsqueda sobre la respuesta y la búsqueda ternaria con problemas de optimización.
Compara los elementos uno a uno en tiempo O(n). No requiere ordenar y, con pocos elementos, suele ser la opción más rápida.
Divide a la mitad un rango ordenado en cada paso y encuentra valores en tiempo O(log n). La versión iterativa solo usa O(1) de memoria adicional.
Devuelven la primera posición cuyo valor es mayor o igual, o estrictamente mayor, que el buscado. Su diferencia cuenta los duplicados, y el módulo bisect de Python ofrece ambas.
La búsqueda paramétrica convierte la pregunta por el menor valor factible en una prueba de sí o no y busca binariamente en el rango de respuestas posibles.
lower_bound devuelve el primer índice cuyo valor es mayor o igual que x, trabajando sobre el rango semiabierto [lo, hi). Si el valor central es menor que x, descarta la mitad izquierda; si no, la derecha. contains usa ese índice para comprobar si el valor está presente, y la última línea confirma que el resultado coincide con bisect.bisect_left de la biblioteca estándar.
searching.py
from bisect import bisect_left
def lower_bound(a, x):
"""Return the first index i with a[i] >= x (len(a) if there is none)."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def contains(a, x):
i = lower_bound(a, x)
return i < len(a) and a[i] == x
if __name__ == "__main__":
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(lower_bound(data, 23), contains(data, 23)) # 5 True
print(lower_bound(data, 24), contains(data, 24)) # 6 False
print(lower_bound(data, 24) == bisect_left(data, 24)) # True
python searching.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Búsqueda.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Búsqueda.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.