En este módulo, aprenderemos sobre los algoritmos de búsqueda, que son fundamentales en la programación y en la informática en general. Los algoritmos de búsqueda permiten encontrar un elemento específico dentro de una estructura de datos, como una lista o un arreglo. Veremos dos de los algoritmos de búsqueda más comunes: la búsqueda lineal y la búsqueda binaria.
Conceptos Clave
- Búsqueda Lineal: Un algoritmo que recorre cada elemento de la estructura de datos hasta encontrar el elemento buscado o hasta llegar al final de la estructura.
- Búsqueda Binaria: Un algoritmo más eficiente que la búsqueda lineal, pero que requiere que la estructura de datos esté ordenada. Divide repetidamente la estructura de datos en mitades para reducir el área de búsqueda.
Búsqueda Lineal
Descripción
La búsqueda lineal es el algoritmo de búsqueda más sencillo. Se utiliza cuando los datos no están ordenados. Este algoritmo recorre la estructura de datos elemento por elemento hasta encontrar el elemento buscado o hasta llegar al final de la estructura.
Ejemplo en Python
def busqueda_lineal(lista, objetivo):
for i in range(len(lista)):
if lista[i] == objetivo:
return i # Retorna el índice donde se encontró el objetivo
return -1 # Retorna -1 si el objetivo no se encuentra en la lista
# Ejemplo de uso
lista = [3, 5, 2, 4, 9]
objetivo = 4
resultado = busqueda_lineal(lista, objetivo)
if resultado != -1:
print(f"Elemento encontrado en el índice {resultado}")
else:
print("Elemento no encontrado")Explicación del Código
- Definición de la función:
busqueda_lineal(lista, objetivo)toma una lista y el elemento objetivo que queremos encontrar. - Bucle for: Recorre cada elemento de la lista.
- Condición: Si el elemento actual es igual al objetivo, retorna el índice del elemento.
- Retorno -1: Si el bucle termina sin encontrar el objetivo, retorna -1.
Ejercicio Práctico
Ejercicio: Implementa una función de búsqueda lineal que, además de retornar el índice del elemento encontrado, también cuente el número de comparaciones realizadas.
def busqueda_lineal_contador(lista, objetivo):
comparaciones = 0
for i in range(len(lista)):
comparaciones += 1
if lista[i] == objetivo:
return i, comparaciones
return -1, comparaciones
# Prueba tu función
lista = [10, 23, 45, 70, 11, 15]
objetivo = 70
indice, comparaciones = busqueda_lineal_contador(lista, objetivo)
print(f"Elemento encontrado en el índice {indice} después de {comparaciones} comparaciones")Búsqueda Binaria
Descripción
La búsqueda binaria es un algoritmo más eficiente que la búsqueda lineal, pero requiere que la lista esté ordenada. Este algoritmo divide repetidamente la lista en mitades y compara el elemento del medio con el objetivo, reduciendo así el área de búsqueda a la mitad en cada paso.
Ejemplo en Python
def busqueda_binaria(lista, objetivo):
inicio = 0
fin = len(lista) - 1
while inicio <= fin:
medio = (inicio + fin) // 2
if lista[medio] == objetivo:
return medio
elif lista[medio] < objetivo:
inicio = medio + 1
else:
fin = medio - 1
return -1
# Ejemplo de uso
lista = [1, 3, 5, 7, 9, 11]
objetivo = 7
resultado = busqueda_binaria(lista, objetivo)
if resultado != -1:
print(f"Elemento encontrado en el índice {resultado}")
else:
print("Elemento no encontrado")Explicación del Código
- Definición de la función:
busqueda_binaria(lista, objetivo)toma una lista ordenada y el elemento objetivo. - Variables inicio y fin: Inicializan los límites de la búsqueda.
- Bucle while: Continúa mientras el inicio sea menor o igual al fin.
- Cálculo del medio: Calcula el índice del elemento medio.
- Condiciones:
- Si el elemento medio es igual al objetivo, retorna el índice.
- Si el elemento medio es menor que el objetivo, ajusta el inicio.
- Si el elemento medio es mayor que el objetivo, ajusta el fin.
- Retorno -1: Si el bucle termina sin encontrar el objetivo, retorna -1.
Ejercicio Práctico
Ejercicio: Implementa una función de búsqueda binaria que, además de retornar el índice del elemento encontrado, también cuente el número de comparaciones realizadas.
def busqueda_binaria_contador(lista, objetivo):
inicio = 0
fin = len(lista) - 1
comparaciones = 0
while inicio <= fin:
comparaciones += 1
medio = (inicio + fin) // 2
if lista[medio] == objetivo:
return medio, comparaciones
elif lista[medio] < objetivo:
inicio = medio + 1
else:
fin = medio - 1
return -1, comparaciones
# Prueba tu función
lista = [2, 4, 6, 8, 10, 12, 14]
objetivo = 10
indice, comparaciones = busqueda_binaria_contador(lista, objetivo)
print(f"Elemento encontrado en el índice {indice} después de {comparaciones} comparaciones")Comparación de Algoritmos
| Algoritmo | Complejidad Temporal | Requiere Lista Ordenada | Ventajas | Desventajas |
|---|---|---|---|---|
| Búsqueda Lineal | O(n) | No | Simple de implementar | Ineficiente para listas grandes |
| Búsqueda Binaria | O(log n) | Sí | Muy eficiente para listas grandes | Requiere lista ordenada |
Conclusión
En esta sección, hemos aprendido sobre dos algoritmos de búsqueda fundamentales: la búsqueda lineal y la búsqueda binaria. La búsqueda lineal es simple y no requiere que la lista esté ordenada, pero puede ser ineficiente para listas grandes. La búsqueda binaria, por otro lado, es mucho más eficiente pero requiere que la lista esté ordenada. Ambos algoritmos son herramientas esenciales en la programación y entender cuándo y cómo utilizarlos es crucial para desarrollar soluciones eficientes.
En el próximo tema, exploraremos los algoritmos de ordenamiento, que son complementarios a los algoritmos de búsqueda y nos permitirán preparar nuestras listas para una búsqueda binaria eficiente.
Fundamentos de la Programación
Módulo 1: Introducción a la Programación
- ¿Qué es la programación?
- Historia de la programación
- Lenguajes de programación
- Entornos de desarrollo