Binäre Suche in C++ mit dynamischem Array

Einführung

Die binäre Suche ist eine Suchmethode, die die Indexposition eines Elements in einem sortierten Array findet. In C++ können wir eine binäre Suche mit zwei Ansätzen durchführen - iterativ und rekursiv. In diesem Lab werden wir eine binäre Suchoperation mit einem dynamischen Array durchführen.

Erstellen Sie eine neue C++-Datei

Zunächst erstellen wir eine neue C++-Datei im Verzeichnis ~/project mit dem Namen main.cpp.

touch ~/project/main.cpp

Headerdateien einbinden

Als nächstes importieren wir die erforderlichen Header-Dateien - iostream, algorithm und vector.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

Erstellen Sie ein dynamisches Array und füllen Sie es mit Elementen

Wir erstellen ein dynamisches Array von ganzen Zahlen, indem wir die vector-Klasse verwenden, und befüllen es mit sortierten ganzen Zahlen.

vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

Binäre Suchfunktion implementieren

Als nächstes implementieren wir die binäre Suchfunktion, die mithilfe des iterativen Ansatzes die Indexposition eines Elements in einem sortierten Array sucht.

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

Rufen Sie die binäre Suchfunktion auf und geben Sie das Ergebnis aus

Schließlich rufen wir die binäre Suchfunktion mit einem Element auf, das gesucht werden soll, und geben das Ergebnis an der Konsole aus.

int target = 7;
int result = binarySearch(arr, target);

if (result == -1) {
    cout << "Element nicht gefunden!" << endl;
} else {
    cout << "Element gefunden an Index " << result << endl;
}

Programm kompilieren und ausführen

Kompilieren und führen Sie das Programm im Terminal aus, indem Sie den folgenden Befehl ausführen:

g++ main.cpp -o main &&./main

Endgültiger Code

Hier ist der vollständige Code der main.cpp-Datei:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    int result = binarySearch(arr, target);

    if (result == -1) {
        cout << "Element nicht gefunden!" << endl;
    } else {
        cout << "Element gefunden an Index " << result << endl;
    }

    return 0;
}

Zusammenfassung

In diesem Lab haben wir gelernt, wie man eine binäre Suche mit einem dynamischen Array in C++ durchführt. Wir haben den iterativen Ansatz verwendet und eine binäre Suchfunktion implementiert, um die Indexposition eines Elements in einem sortierten Array zu suchen. Wir haben auch gelernt, wie man ein dynamisches Array mit der vector-Klasse in C++ erstellt.