Implementar a pesquisa binária em C++

1. Implemente o algoritmo de pesquisa binária para o recipiente std::vector em C++
2. A Análise de Complexidade do Algoritmo de Pesquisa Binária

Este artigo explicará como implementar o algoritmo de pesquisa binária em C++.

Implemente o algoritmo de pesquisa binária para o recipiente std::vector em C++

Os algoritmos de pesquisa são sub-rotinas fundamentais utilizadas na maioria dos problemas comuns e é importante executá-los da maneira mais eficiente. Existem vários tipos de algoritmos de pesquisa; alguns são adaptados para estruturas de dados especiais e alguns podem ser aplicados de forma mais geral.

A pesquisa binária é um algoritmo do tipo dividir e conquistar que deve ser usado em um array classificada de chaves. Geralmente é chamada de pesquisa logarítmica por causa de seu desempenho de pior caso, que apresentaremos uma visão geral mais adiante neste artigo.

Você pode descrever a pesquisa binária da seguinte forma: Assim que tivermos o array ordenado de objetos onde a chave k precisa ser encontrada, devemos comparar a chave fornecida com o elemento do meio no array. Se a chave for menor que o elemento, ela deve estar localizada na metade esquerda do array, ou se for maior - devemos procurá-la na metade direita.

Depois de repetir esse processo de pesquisa recursivamente em cada meio-array menor, eventualmente encontraremos a posição da chave ou indicaremos que a chave não está no array. Embora descrevamos o algoritmo como naturalmente recursivo, ele pode ser implementado usando o método iterativo, mas vamos nos concentrar no recursivo.

O código de exemplo a seguir gera mil inteiros aleatórios no intervalo de [1-1000] e os armazena no contêiner std::vector. O vetor é então classificado usando o algoritmo std::sort e declaramos outro vetor de nove inteiros para pesquisar. Observe que a função de wrapper searchVector é usada para chamar a função recursiva binarySearch.

O último verifica se o primeiro dos índices de duas posições é maior que o outro; em caso afirmativo, a função retorna. O valor de retorno -1 é usado para indicar o status não encontrado para a chave fornecida. Em seguida, a posição do meio é calculada e comparada com a chave, que retorna o valor do índice se verdadeiro. Finalmente, escolhemos qual parte do array precisa ser pesquisada e chamamos a mesma função com os índices correspondentes.

#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;
}

Resultado:

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

A Análise de Complexidade do Algoritmo de Pesquisa Binária

A pesquisa binária tem a complexidade O(log n), daí o nome alternativo - pesquisa logarítmica. Podemos estimar vagamente o tempo de execução de implementações de algoritmos recursivos, analisando o custo de recorrência. Observe que pesquisar o elemento do meio é uma operação de tempo constante e precisamos percorrer metade do array.

No programa a seguir, demonstramos o teste de verificação para nossa função de pesquisa binária usando o algoritmo STL std::sort. Lembre-se, porém, de que essa verificação não é uma verificação formal e apenas fornece um caso de teste rápido durante o processo de implementação do algoritmo para depurar e analisar o comportamento do 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;
}

Resultado:

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