Binär sökalgoritm (Binary Search) i C++- Förklaring, exempel och kod

Den binära sökalgoritmen är ett mer effektivt sätt att söka efter ett specifikt element i en sorterad lista. Till skillnad från linjär sökning, som kontrollerar element sekventiellt, delar binär sökning listan i halvor och jämför målelementet med mittelementet. Denna process upprepas tills målelementet hittas eller sökintervallet blir tomt.

Hur det fungerar

1. Börja med hela den sorterade listan.
2. Hitta mittelementet i det aktuella sökintervallet.
3. Jämför mittelementet med målvärdet.
4. Om mittelementet är lika med målvärdet är sökningen framgångsrik.
5. Om mittelementet är större än målet, sök i den vänstra halvan av intervallet.
6. Om mittelementet är mindre än målet, sök i den högra halvan av intervallet.
7. Upprepa steg 2-6 tills målelementet hittas eller sökintervallet blir tomt.

Exempel

Låt oss överväga en sorterad lista med heltal och vill hitta talet 34 med binär sökning.

Sorterad lista: {12, 23, 34, 45, 56, 67, 89, 90}

1. Börja med hela listan.
2. Mellanelement: 56(position 4). Jämför med 34.
3. 56 är större än 34. Sök i den vänstra halvan.
4. Nytt mittelement: 23(position 1). Jämför med 34.
5. 23 är mindre än 34. Sök i den högra halvan.
6. Nytt mittelement: 45(position 3). Jämför med 34.
7. 45 är större än 34. Sök i den vänstra halvan.
8. Nytt mittelement: 34(position 2). Mål hittat.

Exempelkod 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 givna exemplet binarySearch används funktionen för att hitta talet 34 i en sorterad lista med heltal. Resultatet blir positionen 34 i listan(positionerna börjar från 0) eller -1 om numret inte hittas.