Capítulo 5: Algoritmos de Búsqueda
5.4 Problemas Prácticos
Problema 1: Búsqueda Lineal
Escribe una función en Python para implementar un algoritmo de búsqueda lineal. La función debe tomar una lista y el valor objetivo como parámetros y devolver el índice del valor objetivo si está en la lista, de lo contrario, devolver -1.
Solución:
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1Problema 2: Búsqueda Binaria
Implementa una función en Python para una búsqueda binaria. La función debe tomar una lista ordenada y el valor objetivo como parámetros. Si el valor objetivo está en la lista, devuelve su índice. De lo contrario, devuelve -1.
Solución:
def binary_search(lst, target):
left, right = 0, len(lst) - 1
while left <= right:
mid = (left + right) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Problema 3: Hashing
Supongamos que has implementado una tabla hash con encadenamiento para manejar colisiones. Ahora, se te dan las claves: 10, 22, 31, 4, 15, 28, 17, 88, 59. Escribe una función en Python para construir la tabla hash usando la función hash clave mod 10.
Solución:
def build_hash_table(keys):
hash_table = [[] for _ in range(10)] # Initialize hash table as a list of empty lists
for key in keys:
hash_key = key % 10 # Compute hash key
hash_table[hash_key].append(key) # Insert key into appropriate bucket
return hash_table
keys = [10, 22, 31, 4, 15, 28, 17, 88, 59]
print(build_hash_table(keys))Problema 4: Búsqueda Binaria vs Búsqueda Lineal
Dada una lista de 1000 elementos, ¿en qué punto (número de elementos) se vuelve más rápido usar una búsqueda binaria en lugar de una búsqueda lineal? Explica tu razonamiento.
Estos problemas te ayudarán a practicar lo que has aprendido sobre algoritmos de búsqueda. Las soluciones a los problemas están en la siguiente sección. Como siempre, te animaría a intentar los problemas primero antes de mirar las soluciones. ¡Feliz codificación!
En el próximo capítulo, profundizaremos en los algoritmos de ordenamiento, que son otro aspecto fundamental del pensamiento algorítmico. ¡Espero que estés emocionado de continuar en este viaje!
5.4 Problemas Prácticos
Problema 1: Búsqueda Lineal
Escribe una función en Python para implementar un algoritmo de búsqueda lineal. La función debe tomar una lista y el valor objetivo como parámetros y devolver el índice del valor objetivo si está en la lista, de lo contrario, devolver -1.
Solución:
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1Problema 2: Búsqueda Binaria
Implementa una función en Python para una búsqueda binaria. La función debe tomar una lista ordenada y el valor objetivo como parámetros. Si el valor objetivo está en la lista, devuelve su índice. De lo contrario, devuelve -1.
Solución:
def binary_search(lst, target):
left, right = 0, len(lst) - 1
while left <= right:
mid = (left + right) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Problema 3: Hashing
Supongamos que has implementado una tabla hash con encadenamiento para manejar colisiones. Ahora, se te dan las claves: 10, 22, 31, 4, 15, 28, 17, 88, 59. Escribe una función en Python para construir la tabla hash usando la función hash clave mod 10.
Solución:
def build_hash_table(keys):
hash_table = [[] for _ in range(10)] # Initialize hash table as a list of empty lists
for key in keys:
hash_key = key % 10 # Compute hash key
hash_table[hash_key].append(key) # Insert key into appropriate bucket
return hash_table
keys = [10, 22, 31, 4, 15, 28, 17, 88, 59]
print(build_hash_table(keys))Problema 4: Búsqueda Binaria vs Búsqueda Lineal
Dada una lista de 1000 elementos, ¿en qué punto (número de elementos) se vuelve más rápido usar una búsqueda binaria en lugar de una búsqueda lineal? Explica tu razonamiento.
Estos problemas te ayudarán a practicar lo que has aprendido sobre algoritmos de búsqueda. Las soluciones a los problemas están en la siguiente sección. Como siempre, te animaría a intentar los problemas primero antes de mirar las soluciones. ¡Feliz codificación!
En el próximo capítulo, profundizaremos en los algoritmos de ordenamiento, que son otro aspecto fundamental del pensamiento algorítmico. ¡Espero que estés emocionado de continuar en este viaje!
5.4 Problemas Prácticos
Problema 1: Búsqueda Lineal
Escribe una función en Python para implementar un algoritmo de búsqueda lineal. La función debe tomar una lista y el valor objetivo como parámetros y devolver el índice del valor objetivo si está en la lista, de lo contrario, devolver -1.
Solución:
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1Problema 2: Búsqueda Binaria
Implementa una función en Python para una búsqueda binaria. La función debe tomar una lista ordenada y el valor objetivo como parámetros. Si el valor objetivo está en la lista, devuelve su índice. De lo contrario, devuelve -1.
Solución:
def binary_search(lst, target):
left, right = 0, len(lst) - 1
while left <= right:
mid = (left + right) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Problema 3: Hashing
Supongamos que has implementado una tabla hash con encadenamiento para manejar colisiones. Ahora, se te dan las claves: 10, 22, 31, 4, 15, 28, 17, 88, 59. Escribe una función en Python para construir la tabla hash usando la función hash clave mod 10.
Solución:
def build_hash_table(keys):
hash_table = [[] for _ in range(10)] # Initialize hash table as a list of empty lists
for key in keys:
hash_key = key % 10 # Compute hash key
hash_table[hash_key].append(key) # Insert key into appropriate bucket
return hash_table
keys = [10, 22, 31, 4, 15, 28, 17, 88, 59]
print(build_hash_table(keys))Problema 4: Búsqueda Binaria vs Búsqueda Lineal
Dada una lista de 1000 elementos, ¿en qué punto (número de elementos) se vuelve más rápido usar una búsqueda binaria en lugar de una búsqueda lineal? Explica tu razonamiento.
Estos problemas te ayudarán a practicar lo que has aprendido sobre algoritmos de búsqueda. Las soluciones a los problemas están en la siguiente sección. Como siempre, te animaría a intentar los problemas primero antes de mirar las soluciones. ¡Feliz codificación!
En el próximo capítulo, profundizaremos en los algoritmos de ordenamiento, que son otro aspecto fundamental del pensamiento algorítmico. ¡Espero que estés emocionado de continuar en este viaje!
5.4 Problemas Prácticos
Problema 1: Búsqueda Lineal
Escribe una función en Python para implementar un algoritmo de búsqueda lineal. La función debe tomar una lista y el valor objetivo como parámetros y devolver el índice del valor objetivo si está en la lista, de lo contrario, devolver -1.
Solución:
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1Problema 2: Búsqueda Binaria
Implementa una función en Python para una búsqueda binaria. La función debe tomar una lista ordenada y el valor objetivo como parámetros. Si el valor objetivo está en la lista, devuelve su índice. De lo contrario, devuelve -1.
Solución:
def binary_search(lst, target):
left, right = 0, len(lst) - 1
while left <= right:
mid = (left + right) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Problema 3: Hashing
Supongamos que has implementado una tabla hash con encadenamiento para manejar colisiones. Ahora, se te dan las claves: 10, 22, 31, 4, 15, 28, 17, 88, 59. Escribe una función en Python para construir la tabla hash usando la función hash clave mod 10.
Solución:
def build_hash_table(keys):
hash_table = [[] for _ in range(10)] # Initialize hash table as a list of empty lists
for key in keys:
hash_key = key % 10 # Compute hash key
hash_table[hash_key].append(key) # Insert key into appropriate bucket
return hash_table
keys = [10, 22, 31, 4, 15, 28, 17, 88, 59]
print(build_hash_table(keys))Problema 4: Búsqueda Binaria vs Búsqueda Lineal
Dada una lista de 1000 elementos, ¿en qué punto (número de elementos) se vuelve más rápido usar una búsqueda binaria en lugar de una búsqueda lineal? Explica tu razonamiento.
Estos problemas te ayudarán a practicar lo que has aprendido sobre algoritmos de búsqueda. Las soluciones a los problemas están en la siguiente sección. Como siempre, te animaría a intentar los problemas primero antes de mirar las soluciones. ¡Feliz codificación!
En el próximo capítulo, profundizaremos en los algoritmos de ordenamiento, que son otro aspecto fundamental del pensamiento algorítmico. ¡Espero que estés emocionado de continuar en este viaje!