4.1 Comparación de la complejidad temporal de la búsqueda lineal y binaria
Vamos a comparar la complejidad temporal de la búsqueda lineal y binaria.
Búsqueda lineal:
- Complejidad temporal:
O(n), dondenes el número de elementos en el array o lista. - Mejor caso:
O(1)— el elemento se encuentra en la primera posición. - Promedio:
O(n/2) = O(n)— el elemento se encuentra en promedio en algún lugar del medio. - Peor caso:
O(n)— el elemento se encuentra en la última posición o no está presente.
Búsqueda binaria:
- Complejidad temporal:
O(log n), dondenes el número de elementos en el array o lista. - Mejor caso:
O(1)— el elemento se encuentra en el primer paso (elemento medio). - Promedio:
O(log n)— búsqueda en un array ordenado. - Peor caso:
O(log n)— el elemento se encuentra en el último paso o no está presente.
Ejemplo de análisis de complejidad temporal
Búsqueda lineal:
- Array
[1, 3, 5, 7, 9, 11, 13], elemento buscado 7. - Se verifica cada elemento hasta encontrar el 7 en el índice 3.
- Se requirieron 4 verificaciones, lo que corresponde a
O(n).
Búsqueda binaria:
- Array
[1, 3, 5, 7, 9, 11, 13], elemento buscado7. - El elemento medio (7) se encuentra en el primer paso.
- Se requirió 1 verificación, lo que corresponde a
O(log n).
4.2 Ventajas y desventajas de cada método
Veamos las ventajas y desventajas de cada tipo de búsqueda.
Búsqueda lineal:
Ventajas:
- Sencillez en la implementación: La búsqueda lineal es muy fácil de implementar y entender.
- No hay requisitos para los datos: La búsqueda lineal se puede aplicar a datos no ordenados.
- Adecuado para arrays pequeños: La búsqueda lineal es efectiva para arrays de pequeño tamaño.
Desventajas:
- Baja eficiencia para arrays grandes: La complejidad temporal
O(n)la hace ineficiente para arrays grandes. - Largo tiempo de ejecución: Para arrays grandes, la búsqueda lineal puede tomar mucho tiempo, especialmente si el elemento buscado está más cerca del final del array o no está presente.
Búsqueda binaria:
Ventajas:
- Alta eficiencia para arrays grandes: La complejidad temporal
O(log n)la hace muy eficiente para arrays grandes. - Ejecución rápida: La búsqueda binaria es significativamente más rápida que la búsqueda lineal al trabajar con grandes arrays ordenados.
Desventajas:
- Requisito de datos ordenados: La búsqueda binaria solo funciona con arrays ordenados, lo que podría requerir tiempo adicional para la ordenación previa.
- Complejidad en la implementación: Implementar la búsqueda binaria es más complicado en comparación con la búsqueda lineal.
4.3 Cuándo usar cada búsqueda
Veamos cuándo usar la búsqueda lineal y cuándo la búsqueda binaria.
Búsqueda lineal.
Usa la búsqueda lineal cuando:
- El array o lista no está ordenado.
- El tamaño del array o lista es pequeño.
- Se necesita una solución simple y rápida sin costos adicionales de ordenación.
- Se requiere encontrar la primera aparición o todas las apariciones de un elemento.
- Los datos llegan en tiempo real, y la ordenación previa no es posible o no es razonable.
Búsqueda binaria.
Usa la búsqueda binaria si:
- El array o lista está ordenado.
- El tamaño del array o lista es grande.
- Búsqueda frecuente de elementos en el mismo conjunto de datos (se puede ordenar los datos previamente una vez).
- Es importante una alta velocidad de búsqueda.
- Es aceptable dedicar tiempo a ordenar previamente los datos.
4.4 Ejemplos de tareas para la búsqueda lineal
1. Búsqueda en una lista no ordenada
Se necesita encontrar el índice de un número dado en una lista no ordenada de números.
Ejemplo:
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target)) # Salida: 2
2. Búsqueda de la primera aparición en un array
Se necesita encontrar la primera aparición de un elemento dado en una lista de cadenas.
Ejemplo:
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
words = ["apple", "banana", "cherry", "date", "banana"]
target = "banana"
print(linear_search(words, target)) # Salida: 1
3. Búsqueda en datos en tiempo real
Encontrar un elemento en un flujo de datos que llega en tiempo real.
Ejemplo:
import random
def find_in_stream(stream, target):
for index, element in enumerate(stream):
if element == target:
return index
return -1
stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))
4.5 Ejemplos de tareas para la búsqueda binaria
1. Búsqueda en un array ordenado
Se necesita encontrar el índice de un número dado en un array ordenado de números.
Ejemplo:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target)) # Salida: 3
2. Búsqueda frecuente en un gran conjunto de datos
Buscar frecuentemente elementos en un gran array ordenado de números.
Ejemplo:
import random
sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))
3. Búsqueda de un elemento en una base de datos ordenada
Encontrar un registro en una base de datos ordenada por campo clave.
Ejemplo:
database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
left, right = 0, len(db) - 1
while left <= right:
mid = (left + right) // 2
if db[mid]["id"] == target_id:
return db[mid]
elif db[mid]["id"] < target_id:
left = mid + 1
else:
right = mid - 1
return None
target_id = 54321
print(binary_search_db(database, target_id))
GO TO FULL VERSION