Algorytm wyszukiwania binarnego (Binary Search) w C++- wyjaśnienie, przykład i kod

Algorytm wyszukiwania binarnego jest bardziej wydajnym sposobem wyszukiwania określonego elementu na posortowanej liście. W przeciwieństwie do wyszukiwania liniowego, które sprawdza elementy sekwencyjnie, wyszukiwanie binarne dzieli listę na połowy i porównuje element docelowy z elementem środkowym. Proces ten jest powtarzany do momentu znalezienia elementu docelowego lub wyczerpania zakresu wyszukiwania.

Jak to działa

1. Zacznij od całej posortowanej listy.
2. Znajdź środkowy element bieżącego zakresu wyszukiwania.
3. Porównaj środkowy element z wartością docelową.
4. Jeśli środkowy element jest równy wartości docelowej, wyszukiwanie zakończyło się powodzeniem.
5. Jeśli środkowy element jest większy niż cel, szukaj w lewej połowie zakresu.
6. Jeśli środkowy element jest mniejszy niż cel, szukaj w prawej połowie zakresu.
7. Powtarzaj kroki 2-6, aż element docelowy zostanie znaleziony lub zakres wyszukiwania stanie się pusty.

Przykład

Rozważmy posortowaną listę liczb całkowitych i chcemy znaleźć liczbę 34 za pomocą wyszukiwania binarnego.

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

1. Zacznij od całej listy.
2. Element środkowy: 56(pozycja 4). Porównaj z 34.
3. 56 jest większe niż 34. Szukaj w lewej połowie.
4. Nowy środkowy element: 23(pozycja 1). Porównaj z 34.
5. 23 jest mniejsze niż 34. Szukaj w prawej połowie.
6. Nowy środkowy element: 45(pozycja 3). Porównaj z 34.
7. 45 jest większe niż 34. Szukaj w lewej połowie.
8. Nowy środkowy element: 34(pozycja 2). Znaleziono cel.

Przykładowy kod w 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;  
}  

W podanym przykładzie binarySearch funkcja służy do znalezienia liczby 34 na posortowanej liście liczb całkowitych. Wynikiem będzie pozycja 34 na liście(pozycje zaczynają się od 0) lub -1 jeśli numer nie zostanie znaleziony.