Implementar la búsqueda binaria en C++

1. Implementar el algoritmo de búsqueda binaria para el contenedor std::vector en C++
2. El análisis de complejidad del algoritmo de búsqueda binaria

Este artículo explicará cómo implementar el algoritmo de búsqueda binaria en C++.

Implementar el algoritmo de búsqueda binaria para el contenedor std::vector en C++

Los algoritmos de búsqueda son subrutinas fundamentales que se utilizan en la mayoría de los problemas comunes y es importante ejecutarlos de la manera más eficiente. Hay varios tipos de algoritmos de búsqueda; algunos están diseñados para estructuras de datos especiales y otros se pueden aplicar de manera más general.

La búsqueda binaria es un algoritmo de tipo divide y vencerás que debe usarse en un array ordenada de claves. A menudo se le llama búsqueda logarítmica debido a su desempeño en el peor de los casos, que veremos más adelante en el artículo.

Puede describir la búsqueda binaria de la siguiente manera: Una vez que tenemos el array ordenada de objetos donde se necesita encontrar la clave k, debemos comparar la clave dada con el elemento intermedio del array. Si la clave es menor que el elemento, debe ubicarse en la mitad izquierda del array, o si es más grande, debemos buscarla en la mitad derecha.

Después de repetir este proceso de búsqueda de forma recursiva en cada medio array más pequeño, eventualmente encontraremos la posición de la clave o indicaremos que la clave no está en el array. Aunque describimos el algoritmo como naturalmente recursivo, se puede implementar utilizando el método iterativo, pero nos centraremos en el recursivo.

El siguiente código de ejemplo genera mil enteros aleatorios en el rango de [1-1000] y los almacena en el contenedor std::vector. Luego, el vector se ordena usando el algoritmo std::sort, y declaramos otro vector de nueve enteros para buscar. Tenga en cuenta que la función contenedora searchVector se utiliza para llamar a la función recursiva binarySearch.

Este último comprueba si el primero de los índices de dos posiciones es más que el otro; si es así, la función regresa. El valor de retorno -1 se utiliza para indicar el estado de no encontrado para la clave dada. A continuación, se calcula la posición intermedia y se compara con la clave, que devuelve el valor del índice si es verdadero. Finalmente, elegimos qué parte del array necesita ser buscada y llamamos a la misma función con los índices correspondientes.

#include <iostream>
#include <random>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

constexpr int MIN = 1;
constexpr int MAX = 1000;
constexpr int NUMS_TO_GEN = 1000;

template <typename T>
int binarySearch(const vector<T> &vec, T &item, int s1, int s2) {
  if (s1 > s2) return -1;

  auto middle = (s1 + s2) / 2;

  if (item == vec.at(middle)) return middle;

  if (item > vec.at(middle))
    return binarySearch(vec, item, middle + 1, s2);
  else
    return binarySearch(vec, item, s1, middle - 1);
}

template <typename T>
int searchVector(const vector<T> &vec, T &item) {
  return binarySearch(vec, item, 0, vec.size() - 1);
}

int main() {
  std::random_device rd;
  std::default_random_engine eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  std::vector<int> vec;
  vec.reserve(NUMS_TO_GEN);
  for (int n = 0; n < NUMS_TO_GEN; ++n) {
    vec.push_back(distr(eng));
  }
  std::sort(vec.begin(), vec.end());

  std::vector<int> vec2{2, 111, 222, 5, 333, 7, 8, 444, 100};
  for (auto &item : vec2) {
    searchVector(vec, item) != -1 ? cout << "found, " : cout << "did not, ";
  }
  cout << endl;

  return EXIT_SUCCESS;
}

Producción :

did not, found, found, did not, found, did not, found, did not, found,

El análisis de complejidad del algoritmo de búsqueda binaria

La búsqueda binaria tiene la complejidad O(log n), de ahí el nombre de alias - búsqueda logarítmica. Podemos estimar vagamente el tiempo de ejecución de las implementaciones de algoritmos recursivos analizando el costo de recurrencia. Tenga en cuenta que buscar el elemento del medio es una operación de tiempo constante y necesitamos atravesar la mitad del array.

En el siguiente programa, demostramos la prueba de verificación para nuestra función de búsqueda binaria usando el algoritmo STL std::sort. Sin embargo, tenga en cuenta que esta verificación no es una verificación formal y solo proporciona un caso de prueba rápido durante el proceso de implementación del algoritmo para depurar y analizar el comportamiento del código.

#include <iostream>
#include <random>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

constexpr int MIN = 1;
constexpr int MAX = 1000;
constexpr int NUMS_TO_GEN = 1000;

template <typename T>
int binarySearch(const vector<T> &vec, T &item, int s1, int s2) {
  if (s1 > s2) return -1;

  auto middle = (s1 + s2) / 2;

  if (item == vec.at(middle)) return middle;

  if (item > vec.at(middle))
    return binarySearch(vec, item, middle + 1, s2);
  else
    return binarySearch(vec, item, s1, middle - 1);
}

template <typename T>
int searchVector(const vector<T> &vec, T &item) {
  return binarySearch(vec, item, 0, vec.size() - 1);
}

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  std::vector<int> vec;
  vec.reserve(NUMS_TO_GEN);
  for (int n = 0; n < NUMS_TO_GEN; ++n) {
    vec.push_back(distr(eng));
  }
  std::sort(vec.begin(), vec.end());

  std::vector<int> vec2{2, 111, 222, 5, 333, 7, 8, 444, 100};
  for (auto &item : vec2) {
    searchVector(vec, item) != -1 ? cout << "found, " : cout << "did not, ";
  }
  cout << endl;

  for (auto &item : vec2) {
    std::find(vec.begin(), vec.end(), item) != vec.end() ? cout << "found, "
                                                         : cout << "did not, ";
  }

  return EXIT_SUCCESS;
}

Producción :

found, found, found, found, did not, did not, found, found, found,
found, found, found, found, did not, did not, found, found, found,