Bináris keresési (Binary Search) algoritmus C++ nyelven – magyarázat, példa és kód

A bináris keresési algoritmus hatékonyabb módja egy adott elem megkeresésének egy rendezett listában. Ellentétben a lineáris kereséssel, amely szekvenciálisan ellenőrzi az elemeket, a bináris keresés a listát felére osztja, és összehasonlítja a célelemet a középső elemmel. Ez a folyamat mindaddig ismétlődik, amíg a célelem meg nem található, vagy a keresési tartomány kiürül.

Hogyan működik

1. Kezdje a teljes rendezett listával.
2. Keresse meg az aktuális keresési tartomány középső elemét.
3. Hasonlítsa össze a középső elemet a célértékkel.
4. Ha a középső elem megegyezik a célértékkel, a keresés sikeres.
5. Ha a középső elem nagyobb, mint a cél, keressen a tartomány bal felében.
6. Ha a középső elem kisebb, mint a cél, keressen a tartomány jobb felében.
7. Ismételje meg a 2-6. lépéseket, amíg meg nem találja a célelemet, vagy amíg a keresési tartomány kiürül.

Példa

Tekintsük az egész számok rendezett listáját, és keressük meg a 34-es számot bináris kereséssel.

Rendezett lista: {12, 23, 34, 45, 56, 67, 89, 90}

1. Kezdje a teljes listával.
2. Középső elem: 56(4. pozíció). Hasonlítsd össze a 34-el.
3. 56 nagyobb, mint 34. Keresés a bal felében.
4. Új középső elem: 23(1. pozíció). Hasonlítsd össze a 34-el.
5. A 23 kisebb, mint a 34. Keressen a jobb oldalon.
6. Új középső elem: 45(3. pozíció). Hasonlítsd össze a 34-el.
7. 45 nagyobb, mint 34. Keresés a bal felében.
8. Új középső elem: 34(2. pozíció). Cél megtalálva.

Példakód C++ nyelven

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

Az adott példában a binarySearch függvény a 34-es szám megkeresésére szolgál az egész számok rendezett listájában. Az eredmény a 34. pozíció lesz a listában(a pozíciók 0-tól kezdődnek), vagy -1, ha a szám nem található.