Búsqueda binaria

2.1 Definición de búsqueda binaria y sus conceptos básicos

Búsqueda binaria — es un algoritmo de búsqueda de un elemento en un array ordenado, que trabaja dividiendo el array a la mitad. Este algoritmo es significativamente más eficiente que la búsqueda lineal para arrays grandes, ya que reduce el número de comprobaciones al dividir el array en dos partes en cada iteración.

Conceptos básicos:

• Array ordenado: La búsqueda binaria funciona solo en arrays ordenados.
• División a la mitad: El algoritmo compara el elemento buscado con el elemento en el medio del array.
• División recursiva o iterativa: Si el elemento buscado es menor que el medio, la búsqueda continúa en la mitad izquierda del array, de lo contrario, en la derecha.
• Condición de terminación: La búsqueda se detiene cuando se encuentra el elemento o el rango de búsqueda se vuelve vacío.

¡Importante! Para la búsqueda binaria se necesita un array ordenado.

Para un correcto funcionamiento de la búsqueda binaria, los datos de entrada deben estar ordenados de forma ascendente. Este es el único requisito, ya que el algoritmo se basa en el hecho de que los elementos del array están ordenados. Gracias a esto, puede excluir eficientemente la mitad de los elementos en cada paso de la búsqueda.

Ejemplo de un array ordenado:

sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 Implementación paso a paso de la búsqueda binaria

Principio de funcionamiento de la búsqueda binaria:

1. Inicialización: Establecer los límites iniciales de la búsqueda (límites izquierdo y derecho del array).
2. Elección del elemento medio: Encontrar el índice del elemento medio del array.
3. Comparación: Comparar el elemento medio con el valor buscado.
4. Actualización de los límites:
   1. Si el elemento medio es igual al valor buscado, devolver su índice.
   2. Si el valor buscado es menor que el elemento medio, actualizar el límite derecho de búsqueda.
   3. Si es mayor, actualizar el límite izquierdo.
5. Repetición: Repetir los pasos 2-4 hasta encontrar el elemento o hasta que el límite izquierdo sea mayor que el derecho.

Algoritmo paso a paso:

1. Inicialización: Establecer left en 0 y right en len(arr) - 1.
2. Calcular el elemento medio: mid = (left + right) // 2
3. Comparar con el elemento objetivo:
   1. Si arr[mid] == target, devolver mid
   2. Si arr[mid] < target, actualizar left = mid + 1
   3. Si arr[mid] > target, actualizar right = mid - 1
4. Repetir: Volver al paso 2 hasta que left <= right
5. Si el elemento no se encuentra: Devolver -1

Implementación iterativa de la búsqueda binaria en Python:

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

2.3 Complejidad temporal de la búsqueda binaria O(log n)

La búsqueda binaria tiene una complejidad temporal de O(log n), donde n es el número de elementos en el array. Esto significa que en cada paso el algoritmo divide la cantidad de elementos a la mitad, lo que acelera significativamente la búsqueda en comparación con la búsqueda lineal, que tiene una complejidad temporal de O(n).

Análisis de la complejidad temporal:

• Mejor caso (Best case): El elemento se encuentra en el primer paso, O(1).
• Promedio (Average case): O(log n).
• Peor caso (Worst case): El elemento se encuentra en el último paso o está ausente, O(log n).

Ejemplo para el análisis de la complejidad temporal:

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

# El algoritmo realizó 3 pasos (logaritmo de 7 elementos) para encontrar el elemento, 
# lo que corresponde a O(log n)

Representación gráfica de la complejidad:

Imagínate un array de 16 elementos.

Supongamos que estamos buscando el elemento 15, entonces los pasos serían:

Primer paso. Verifica el elemento medio (quedan 8 elementos).

Segundo paso. Verifica el elemento medio en la mitad restante (quedan 4 elementos).

Tercer paso. Verifica el elemento medio en la mitad restante (quedan 2 elementos).

Cuarto paso. Verifica el último elemento (quedan 1 elemento).

Como resultado, el algoritmo realizará 4 pasos para un array de 16 elementos, lo que corresponde al logaritmo en base 2 de 16, es decir, log2(16) = 4. Esto es la complejidad logarítmica O(log n).