Algoritem binarnega iskanja (Binary Search) v C++ – razlaga, primer in koda

Binarni iskalni algoritem je učinkovitejši način iskanja določenega elementa na razvrščenem seznamu. Za razliko od linearnega iskanja, ki preverja elemente zaporedno, binarno iskanje razdeli seznam na polovice in primerja ciljni element s srednjim elementom. Ta postopek se ponavlja, dokler ni najden ciljni element ali dokler ni iskalno območje prazno.

Kako deluje

1. Začnite s celotnim razvrščenim seznamom.
2. Poiščite srednji element trenutnega obsega iskanja.
3. Primerjajte srednji element s ciljno vrednostjo.
4. Če je srednji element enak ciljni vrednosti, je iskanje uspešno.
5. Če je srednji element večji od cilja, iščite v levi polovici obsega.
6. Če je srednji element manjši od cilja, iščite v desni polovici obsega.
7. Ponavljajte korake 2–6, dokler ne najdete ciljnega elementa ali dokler iskalni obseg ne postane prazen.

Primer

Razmislimo o razvrščenem seznamu celih števil in želimo poiskati število 34 z uporabo binarnega iskanja.

Razvrščen seznam: {12, 23, 34, 45, 56, 67, 89, 90}

1. Začnite s celotnim seznamom.
2. Srednji element: 56(položaj 4). Primerjaj s 34.
3. 56 je večje od 34. Iskanje v levi polovici.
4. Nov srednji element: 23(položaj 1). Primerjaj s 34.
5. 23 je manjše od 34. Iskanje v desni polovici.
6. Nov srednji element: 45(položaj 3). Primerjaj s 34.
7. 45 je večje od 34. Iskanje v levi polovici.
8. Nov srednji element: 34(položaj 2). Tarča najdena.

Primer kode v 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;  
}  

V danem primeru binarySearch je funkcija uporabljena za iskanje števila 34 na razvrščenem seznamu celih števil. Rezultat bo položaj 34 na seznamu(položaji se začnejo z 0) ali -1, če številka ni najdena.