Implementieren der binären Suche in C++

1. Implementieren Sie den binären Suchalgorithmus für den Container std::vector in C++
2. Die Komplexitätsanalyse des binären Suchalgorithmus

In diesem Artikel wird erläutert, wie Sie den binären Suchalgorithmus in C++ implementieren.

Implementieren Sie den binären Suchalgorithmus für den Container std::vector in C++

Suchalgorithmen sind grundlegende Unterroutinen, die in den häufigsten Problemen verwendet werden, und es ist wichtig, sie auf die effizienteste Weise auszuführen. Es gibt verschiedene Arten von Suchalgorithmen; einige sind auf spezielle Datenstrukturen zugeschnitten, andere lassen sich allgemeiner anwenden.

Die binäre Suche ist ein Algorithmus vom Typ Divide-and-Conquer, der für ein sortiertes Array von Schlüsseln verwendet werden sollte. Sie wird wegen ihrer Worst-Case-Leistung oft als logarithmische Suche bezeichnet, die wir später in diesem Artikel noch einmal zusammenfassen werden.

Sie können die binäre Suche wie folgt beschreiben: Sobald wir das sortierte Array von Objekten haben, in denen der Schlüssel k gefunden werden muss, sollten wir den angegebenen Schlüssel mit dem mittleren Element im Array vergleichen. Wenn der Schlüssel kleiner als das Element ist, sollte er sich in der linken Hälfte des Arrays befinden, oder wenn er größer ist, sollten wir in der rechten Hälfte danach suchen.

Nachdem wir diesen Nachschlageprozess rekursiv für jedes kleinere Halbarray wiederholt haben, werden wir schließlich die Position des Schlüssels finden oder angeben, dass der Schlüssel nicht im Array enthalten ist. Obwohl wir den Algorithmus als natürlich rekursiv beschreiben, kann er mit der iterativen Methode implementiert werden, aber wir konzentrieren uns auf die rekursive Methode.

Der folgende Beispielcode generiert tausend zufällige Ganzzahlen im Bereich [1-1000] und speichert sie im Container std::vector. Der Vektor wird dann mit dem Algorithmus std::sort sortiert, und wir deklarieren einen weiteren Vektor mit neun ganzen Zahlen, nach denen gesucht werden soll. Beachten Sie, dass die Wrapper-Funktion searchVector verwendet wird, um die rekursive Funktion binarySearch aufzurufen.

Letzterer prüft, ob der erste von zweistelligen Indizes mehr ist als der andere; wenn ja, kehrt die Funktion zurück. Der Rückgabewert -1 wird verwendet, um den Nicht-gefunden-Status für den angegebenen Schlüssel anzuzeigen. Als nächstes wird die mittlere Position berechnet und mit dem Schlüssel verglichen, der bei true den Indexwert zurückgibt. Schließlich wählen wir aus, welcher Teil des Arrays durchsucht werden soll und rufen dieselbe Funktion mit den entsprechenden Indizes auf.

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

Ausgabe:

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

Die Komplexitätsanalyse des binären Suchalgorithmus

Die binäre Suche hat die Komplexität O(log n), daher der Aliasname - logarithmische Suche. Wir können die Laufzeit rekursiver Algorithmus-Implementierungen grob schätzen, indem wir die Rekursionskosten analysieren. Beachten Sie, dass das Nachschlagen des mittleren Elements eine konstante Zeitoperation ist und wir die Hälfte des Arrays durchlaufen müssen.

Im folgenden Programm demonstrieren wir den Verifikationstest für unsere binäre Suchfunktion mit dem STL-Algorithmus std::sort. Beachten Sie jedoch, dass diese Prüfung keine formale Überprüfung ist und nur einen schnellen Testfall während des Algorithmusimplementierungsprozesses bietet, um das Codeverhalten zu debuggen und zu analysieren.

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

Ausgabe:

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