close

Binärer Suchalgorithmus (Binary Search) in C++ – Erklärung, Beispiel und Code

Der binäre Suchalgorithmus ist eine effizientere Methode zur Suche nach einem bestimmten Element in einer sortierten Liste. Im Gegensatz zur linearen Suche, bei der Elemente nacheinander überprüft werden, teilt die binäre Suche die Liste in zwei Hälften und vergleicht das Zielelement mit dem mittleren Element. Dieser Vorgang wird wiederholt, bis das Zielelement gefunden wird oder der Suchbereich leer wird.

Wie es funktioniert

  1. Beginnen Sie mit der gesamten sortierten Liste.
  2. Suchen Sie das mittlere Element des aktuellen Suchbereichs.
  3. Vergleichen Sie das mittlere Element mit dem Zielwert.
  4. Wenn das mittlere Element dem Zielwert entspricht, ist die Suche erfolgreich.
  5. Wenn das mittlere Element größer als das Ziel ist, suchen Sie in der linken Hälfte des Bereichs.
  6. Wenn das mittlere Element kleiner als das Ziel ist, suchen Sie in der rechten Hälfte des Bereichs.
  7. Wiederholen Sie die Schritte 2–6, bis das Zielelement gefunden wird oder der Suchbereich leer wird.

Beispiel

Betrachten wir eine sortierte Liste von ganzen Zahlen und möchten mithilfe der binären Suche die Zahl 34 finden.

Sortierte Liste: {12, 23, 34, 45, 56, 67, 89, 90}

  1. Beginnen Sie mit der gesamten Liste.
  2. Mittelelement: 56(Position 4). Vergleiche mit 34.
  3. 56 ist größer als 34. Suchen Sie in der linken Hälfte.
  4. Neues Mittelelement: 23(Position 1). Vergleiche mit 34.
  5. 23 ist kleiner als 34. Suchen Sie in der rechten Hälfte.
  6. Neues Mittelelement: 45(Position 3). Vergleiche mit 34.
  7. 45 ist größer als 34. Suchen Sie in der linken Hälfte.
  8. Neues Mittelelement: 34(Position 2). Ziel gefunden.

Beispielcode in C++ 

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}

Im gegebenen Beispiel binarySearch wird die Funktion verwendet, um die Zahl 34 in einer sortierten Liste von Ganzzahlen zu finden. Das Ergebnis ist die Position 34 in der Liste(Positionen beginnen bei 0) oder -1, wenn die Nummer nicht gefunden wird.