Algoritmo de búsqueda binaria (Binary Search) en C++: explicación, ejemplo y código

El algoritmo de búsqueda binaria es una forma más eficiente de buscar un elemento específico en una lista ordenada. A diferencia de la búsqueda lineal, que verifica los elementos secuencialmente, la búsqueda binaria divide la lista en mitades y compara el elemento de destino con el elemento del medio. Este proceso se repite hasta que se encuentra el elemento de destino o el rango de búsqueda queda vacío.

Cómo funciona

1. Comience con toda la lista ordenada.
2. Encuentre el elemento medio del rango de búsqueda actual.
3. Compare el elemento central con el valor objetivo.
4. Si el elemento central es igual al valor objetivo, la búsqueda es exitosa.
5. Si el elemento medio es mayor que el objetivo, busque en la mitad izquierda del rango.
6. Si el elemento central es más pequeño que el objetivo, busque en la mitad derecha del rango.
7. Repita los pasos 2 a 6 hasta que se encuentre el elemento de destino o el rango de búsqueda quede vacío.

Ejemplo

Consideremos una lista ordenada de enteros y queramos encontrar el número 34 usando una búsqueda binaria.

Lista ordenada: {12, 23, 34, 45, 56, 67, 89, 90}

1. Comience con la lista completa.
2. Elemento medio: 56(posición 4). Comparar con 34.
3. 56 es mayor que 34. Busque en la mitad izquierda.
4. Nuevo elemento central: 23(posición 1). Comparar con 34.
5. 23 es más pequeño que 34. Busca en la mitad derecha.
6. Nuevo elemento central: 45(posición 3). Comparar con 34.
7. 45 es mayor que 34. Busque en la mitad izquierda.
8. Nuevo elemento central: 34(posición 2). Objetivo encontrado.

Código de ejemplo en C++

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

En el ejemplo dado, la binarySearch función se usa para encontrar el número 34 en una lista ordenada de enteros. El resultado será la posición 34 en la lista(las posiciones comienzan desde 0) o -1 si no se encuentra el número.