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

Den binære søgealgoritme er en mere effektiv måde at søge efter et bestemt element i en sorteret liste. I modsætning til lineær søgning, som kontrollerer elementer sekventielt, deler binær søgning listen i halvdele og sammenligner målelementet med det midterste element. Denne proces gentages, indtil målelementet er fundet, eller søgeområdet bliver tomt.

Hvordan det virker

1. Start med hele den sorterede liste.
2. Find det midterste element i det aktuelle søgeområde.
3. Sammenlign det midterste element med målværdien.
4. Hvis det midterste element er lig med målværdien, er søgningen vellykket.
5. Hvis det midterste element er større end målet, søg i venstre halvdel af området.
6. Hvis det midterste element er mindre end målet, søg i højre halvdel af området.
7. Gentag trin 2-6, indtil målelementet er fundet, eller søgeområdet bliver tomt.

Eksempel

Lad os overveje en sorteret liste over heltal og ønsker at finde tallet 34 ved hjælp af binær søgning.

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

1. Start med hele listen.
2. Mellemelement: 56(position 4). Sammenlign med 34.
3. 56 er større end 34. Søg i venstre halvdel.
4. Nyt midterelement: 23(position 1). Sammenlign med 34.
5. 23 er mindre end 34. Søg i højre halvdel.
6. Nyt midterelement: 45(position 3). Sammenlign med 34.
7. 45 er større end 34. Søg i venstre halvdel.
8. Nyt midterelement: 34(position 2). Mål fundet.

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 givne eksempel binarySearch bruges funktionen til at finde tallet 34 i en sorteret liste over heltal. Resultatet vil være positionen 34 på listen(positionerne starter fra 0) eller -1, hvis tallet ikke findes.