Binäärihakualgoritmi (Binary Search) C++:ssa- selitys, esimerkki ja koodi

Binäärihakualgoritmi on tehokkaampi tapa etsiä tiettyä elementtiä lajitetusta luettelosta. Toisin kuin lineaarisessa haussa, joka tarkistaa elementit peräkkäin, binäärihaku jakaa listan puoliksi ja vertaa kohdeelementtiä keskielementtiin. Tätä prosessia toistetaan, kunnes kohdeelementti löytyy tai hakualue tyhjenee.

Kuinka se toimii

1. Aloita koko lajitetusta luettelosta.
2. Etsi nykyisen hakualueen keskimmäinen elementti.
3. Vertaa keskimmäistä elementtiä tavoitearvoon.
4. Jos keskimmäinen elementti on yhtä suuri kuin tavoitearvo, haku onnistuu.
5. Jos keskimmäinen elementti on suurempi kuin tavoite, hae alueen vasemmasta puoliskosta.
6. Jos keskimmäinen elementti on pienempi kuin kohde, hae alueen oikealta puoliskolta.
7. Toista vaiheita 2-6, kunnes kohdeelementti löytyy tai hakualue tyhjenee.

Esimerkki

Tarkastellaan lajiteltua kokonaislukuluetteloa ja halutaan löytää luku 34 binäärihaun avulla.

Lajiteltu luettelo: {12, 23, 34, 45, 56, 67, 89, 90}

1. Aloita koko luettelosta.
2. Keskielementti: 56(asento 4). Vertaa 34:ään.
3. 56 on suurempi kuin 34. Hae vasemmasta puoliskosta.
4. Uusi keskielementti: 23(asento 1). Vertaa 34:ään.
5. 23 on pienempi kuin 34. Hae oikeasta puoliskosta.
6. Uusi keskielementti: 45(asento 3). Vertaa 34:ään.
7. 45 on suurempi kuin 34. Hae vasemmasta puoliskosta.
8. Uusi keskielementti: 34(asento 2). Kohde löydetty.

Esimerkkikoodi C++:ssa

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

Esitetyssä esimerkissä binarySearch funktiota käytetään etsimään luku 34 järjestetystä kokonaislukuluettelosta. Tuloksena on paikka 34 luettelossa(paikat alkavat 0:sta) tai -1, jos numeroa ei löydy.