Ejemplos de problemas para búsqueda lineal y binaria

3.1 Problema para encontrar un elemento en un array usando búsqueda lineal

Problema: Se da un array de números. Es necesario encontrar el índice de un número dado utilizando búsqueda lineal. Si el número no se encuentra, devuelve -1.

Ejemplo:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Ejemplo de uso:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Elemento {target} encontrado en el índice {result}")  # Salida: Elemento 7 encontrado en el índice 2

# Ejemplo de uso para un elemento que no está en el array:
target = 5
result = linear_search(arr, target)
print(f"Elemento {target} encontrado en el índice {result}")  # Salida: Elemento 5 encontrado en el índice -1

Explicación:

• La función linear_search recorre cada elemento del array arr y lo compara con target.
• Si se encuentra el elemento, se devuelve su índice.
• Si se han comprobado todos los elementos y el valor buscado no se encuentra, la función devuelve -1.

Ejecutando paso a paso:

1. Array [4, 2, 7, 1, 9, 3] y valor buscado 7.
2. Inicio de la búsqueda: se compara el primer elemento (4) con 7 — no coincide.
3. Pasar al siguiente elemento (2) — no coincide.
4. Pasar al siguiente elemento (7) — coincide.
5. Devolver índice 2.

3.2 Problema para encontrar un elemento en un array ordenado usando búsqueda binaria

Problema: Se da un array ordenado de números. Es necesario encontrar el índice de un número dado utilizando búsqueda binaria. Si el número no se encuentra, devuelve -1.

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

# Ejemplo de uso:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Elemento {target} encontrado en el índice {result}")  # Salida: Elemento 7 encontrado en el índice 3

# Ejemplo de uso para un elemento que no está en el array:
target = 6
result = binary_search(sorted_array, target)
print(f"Elemento {target} encontrado en el índice {result}")  # Salida: Elemento 6 encontrado en el índice -1

Explicación:

• La función binary_search usa dos punteros (left y right) para rastrear los límites de la búsqueda en el array arr.
• En cada iteración se encuentra el elemento medio del array y se compara con target.
• Si el elemento medio es igual a target, se devuelve su índice.
• Si target es menor que el elemento medio, la búsqueda continúa en la mitad izquierda del array.
• Si target es mayor que el elemento medio, la búsqueda continúa en la mitad derecha del array.
• Si los límites se cruzan y no se encuentra el elemento, se devuelve -1.

Ejecutando paso a paso:

1. Array ordenado [1, 3, 5, 7, 9, 11, 13] y valor buscado 7.
2. Límites iniciales de búsqueda: left = 0, right = 6.
3. Encontrar el elemento medio: mid = (0 + 6) // 2 = 3.
4. Comparación del elemento medio (7) con target (7) — coincide.
5. Devolver índice 3.

3.3 Comparación y elección del algoritmo de búsqueda adecuado para diferentes problemas

Comparación de búsqueda lineal y binaria:

Elección del algoritmo adecuado

Búsqueda lineal:

• Se usa cuando los datos no están ordenados.
• Adecuado para arrays o listas pequeños.
• Se aplica cuando el número de elementos es pequeño y el tiempo de ejecución no es crítico.

Búsqueda binaria:

• Se aplica cuando los datos están ordenados.
• Ideal para arrays grandes, donde la velocidad de búsqueda importa.
• Eficiente si se requiere búsqueda frecuente en el mismo conjunto de datos (se pueden ordenar previamente los datos).

3.4 Ejercicios prácticos para reforzar el material

Ejercicio 1: Búsqueda lineal

Se da un array de números. Escribe una función para buscar un número dado utilizando búsqueda lineal. La función debe devolver el índice del elemento encontrado o -1 si no se encuentra el elemento.

Ejemplo:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Ejemplo de uso:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Elemento {target} encontrado en el índice {result}")  # Salida: Elemento 7 encontrado en el índice 2

# Pruebas adicionales:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Ejercicio 2: Búsqueda binaria

Se da un array ordenado de números. Escribe una función para buscar un número dado utilizando búsqueda binaria. La función debe devolver el índice del elemento encontrado o -1 si no se encuentra el elemento.

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

# Ejemplo de uso:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Elemento {target} encontrado en el índice {result}")  # Salida: Elemento 7 encontrado en el índice 3

# Pruebas adicionales:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Ejercicio 3: Comparación de búsqueda lineal y binaria

Se da un array de números. Escribe dos funciones para buscar un número dado: una utilizando búsqueda lineal y otra utilizando búsqueda binaria. Compara el rendimiento de ambas funciones en arrays grandes.

Ejemplo:

import time
import random

# Búsqueda lineal
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Búsqueda binaria
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

# Generación de un array grande
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# Comparación de rendimiento
start_time = time.time()
linear_search(large_array, target)
print(f"Búsqueda lineal tomó: {time.time() - start_time:.6f} segundos")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Búsqueda binaria tomó: {time.time() - start_time:.6f} segundos")