Algoritam binarnog pretraživanja (Binary Search) u C++- objašnjenje, primjer i kod

Algoritam binarnog pretraživanja je učinkovitiji način traženja određenog elementa na sortiranom popisu. Za razliku od linearnog pretraživanja, koje provjerava elemente sekvencijalno, binarno pretraživanje dijeli popis na pola i uspoređuje ciljni element sa srednjim elementom. Ovaj se postupak ponavlja sve dok se ciljni element ne pronađe ili dok raspon pretraživanja ne postane prazan.

Kako radi

1. Počnite s cijelim sortiranim popisom.
2. Pronađite srednji element trenutnog raspona pretraživanja.
3. Usporedite srednji element s ciljnom vrijednošću.
4. Ako je srednji element jednak ciljnoj vrijednosti, pretraga je uspješna.
5. Ako je srednji element veći od cilja, tražite u lijevoj polovici raspona.
6. Ako je srednji element manji od cilja, tražite u desnoj polovici raspona.
7. Ponavljajte korake 2-6 dok se ciljni element ne pronađe ili dok raspon pretraživanja ne postane prazan.

Primjer

Razmotrimo sortirani popis cijelih brojeva i želimo pronaći broj 34 pomoću binarnog pretraživanja.

Poredani popis: {12, 23, 34, 45, 56, 67, 89, 90}

1. Počnite s cijelim popisom.
2. Srednji element: 56(pozicija 4). Usporedi s 34.
3. 56 je veće od 34. Traži u lijevoj polovici.
4. Novi srednji element: 23(pozicija 1). Usporedi s 34.
5. 23 je manje od 34. Traži u desnoj polovici.
6. Novi srednji element: 45(pozicija 3). Usporedi s 34.
7. 45 je veće od 34. Traži u lijevoj polovici.
8. Novi srednji element: 34(pozicija 2). Meta pronađena.

Primjer koda u 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;  
}  

U navedenom primjeru, binarySearch funkcija se koristi za pronalaženje broja 34 u sortiranom popisu cijelih brojeva. Rezultat će biti pozicija 34 na popisu(pozicije počinju od 0) ili -1 ako broj nije pronađen.