Heim >Backend-Entwicklung >C++ >So verwenden Sie den binären Suchalgorithmus in C++

So verwenden Sie den binären Suchalgorithmus in C++

WBOY
WBOYOriginal
2023-09-22 08:24:251120Durchsuche

So verwenden Sie den binären Suchalgorithmus in C++

So verwenden Sie den binären Suchalgorithmus in C++

Der binäre Suchalgorithmus (Binary Search) ist ein effizienter Suchalgorithmus, der einen geordneten Datensatz in zwei Hälften teilt und jedes Mal in der Mitte des Datensatzes eine Suche durchführt und den Suchbereich kontinuierlich eingrenzen, indem der Wert in der Mittelposition mit dem Zielwert verglichen wird, bis der Zielwert gefunden wird oder festgestellt wird, dass der Zielwert nicht existiert. Im Folgenden wird die Verwendung des binären Suchalgorithmus in C++ vorgestellt und spezifische Codebeispiele gegeben.

  1. Bestimmen Sie den Suchbereich
    Bevor Sie den binären Suchalgorithmus verwenden, müssen Sie zunächst sicherstellen, dass der zu durchsuchende Datensatz geordnet ist. Zum Beispiel haben wir ein geordnetes Array von ganzen Zahlen, in dem wir nach einem bestimmten Zielwert suchen möchten.
  2. Binäre Suchfunktion definieren
    In C++ können wir eine Funktion definieren, um den binären Suchalgorithmus zu implementieren. Zu den Eingabeparametern dieser Funktion gehören das zu durchsuchende Array, die Start- und Endposition des Arrays sowie der Zielwert target. Der Rückgabewert der Funktion ist der Index des Zielwerts im Array. Wenn der Zielwert nicht vorhanden ist, kann ein bestimmter Wert (z. B. -1) zurückgegeben werden.

Die spezifische Funktionsdefinition lautet wie folgt:

int binarySearch(int nums[], int start, int end, int target) {
    // 定义二分搜索的起始位置和结束位置
    int left = start;
    int right = end;
    
    while (left <= right) {
        // 计算中间位置
        int mid = left + (right - left) / 2;
        
        // 如果中间位置的值等于目标值,直接返回索引
        if (nums[mid] == target) {
            return mid;
        }
        
        // 如果中间位置的值大于目标值,更新结束位置
        else if (nums[mid] > target) {
            right = mid - 1;
        }
        
        // 如果中间位置的值小于目标值,更新起始位置
        else {
            left = mid + 1;
        }
    }
    
    // 目标值不存在,返回-1
    return -1;
}
  1. Binäre Suchfunktion aufrufen
    Durch Aufrufen der binären Suchfunktion können wir den Index des Zielwerts im Array abrufen. Wir haben beispielsweise ein geordnetes Array „nums“ und möchten nach dem Zielwert „target“ suchen. Die binäre Suchfunktion kann mit dem folgenden Code aufgerufen werden:
int nums[] = {1, 3, 5, 7, 9};
int n = sizeof(nums) / sizeof(nums[0]);
int target = 5;
int index = binarySearch(nums, 0, n - 1, target);

if (index != -1) {
    cout << "目标值的索引为:" << index << endl;
}
else {
    cout << "目标值不存在!" << endl;
}

Im obigen Code definieren wir zunächst ein geordnetes Array nums und berechnen dann die Länge n des Arrays. Anschließend wird der Zielwert definiert und die binäre Suchfunktion „binarySearch“ aufgerufen, um den Index des Zielwerts zu durchsuchen. Schließlich basiert die Ausgabe auf dem von der Funktion zurückgegebenen Ergebnis.

Durch die oben genannten Schritte können wir den binären Suchalgorithmus in C++ verwenden, um effiziente Suchvorgänge durchzuführen. In tatsächlichen Anwendungen kann die binäre Suchfunktion entsprechend bestimmten Szenarien und Anforderungen aufgerufen und die weitere Verarbeitung basierend auf den zurückgegebenen Ergebnissen durchgeführt werden.

Zusammenfassung
Der binäre Suchalgorithmus ist ein effizienter Suchalgorithmus, der für geordnete Datensammlungen geeignet ist. In C++ können wir suchen, indem wir eine binäre Suchfunktion definieren und das zu durchsuchende Array, die Startposition, die Endposition und den Zielwert übergeben. Durch kontinuierliche Aktualisierung des Suchbereichs kann schließlich der Index des Zielwerts gefunden werden. Wir hoffen, dass die Einführung und die Codebeispiele in diesem Artikel den Lesern helfen können, den binären Suchalgorithmus besser zu verstehen und anzuwenden.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den binären Suchalgorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn