Binær søkealgoritme (Binary Search) i C++- Forklaring, eksempel og kode

Den binære søkealgoritmen er en mer effektiv måte å søke etter et spesifikt element i en sortert liste. I motsetning til lineært søk, som sjekker elementer sekvensielt, deler binært søk listen i halvdeler og sammenligner målelementet med midtelementet. Denne prosessen gjentas til målelementet er funnet eller søkeområdet blir tomt.

Hvordan det fungerer

1. Start med hele den sorterte listen.
2. Finn midtelementet i gjeldende søkeområde.
3. Sammenlign det midterste elementet med målverdien.
4. Hvis det midterste elementet er lik målverdien, er søket vellykket.
5. Hvis det midterste elementet er større enn målet, søk i venstre halvdel av området.
6. Hvis det midterste elementet er mindre enn målet, søk i høyre halvdel av området.
7. Gjenta trinn 2-6 til målelementet er funnet eller søkeområdet blir tomt.

Eksempel

La oss vurdere en sortert liste over heltall og ønsker å finne tallet 34 ved hjelp av binært søk.

Sortert liste: {12, 23, 34, 45, 56, 67, 89, 90}

1. Start med hele listen.
2. Mellomelement: 56(posisjon 4). Sammenlign med 34.
3. 56 er større enn 34. Søk i venstre halvdel.
4. Nytt midtelement: 23(posisjon 1). Sammenlign med 34.
5. 23 er mindre enn 34. Søk i høyre halvdel.
6. Nytt midtelement: 45(posisjon 3). Sammenlign med 34.
7. 45 er større enn 34. Søk i venstre halvdel.
8. Nytt midtelement: 34(posisjon 2). Mål funnet.

Eksempelkode i 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;  
}  

I det gitte eksemplet binarySearch brukes funksjonen til å finne tallet 34 i en sortert liste over heltall. Resultatet vil være posisjonen 34 i listen(posisjonene starter fra 0) eller -1 hvis tallet ikke finnes.