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.

Skills Graph

Erstellen einer neuen C++-Datei

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

touch ~/project/main.cpp

Header-Dateien einbinden

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

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

using namespace std;

Erstellen eines dynamischen Arrays und Befüllen 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};

Implementieren der binären Suchfunktion

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 der binären Suchfunktion auf und Ausgabe des Ergebnisses

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

Kompilieren und Ausführen des Programms

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.