Binární vyhledávací (Binary Search) algoritmus v C++- vysvětlení, příklad a kód

Binární vyhledávací algoritmus je efektivnější způsob hledání konkrétního prvku v seřazeném seznamu. Na rozdíl od lineárního vyhledávání, které kontroluje prvky postupně, binární vyhledávání rozděluje seznam na poloviny a porovnává cílový prvek se středním prvkem. Tento proces se opakuje, dokud není nalezen cílový prvek nebo dokud se oblast hledání nevyprázdní.

Jak to funguje

1. Začněte s celým seřazeným seznamem.
2. Najděte prostřední prvek aktuálního rozsahu vyhledávání.
3. Porovnejte prostřední prvek s cílovou hodnotou.
4. Pokud se prostřední prvek rovná cílové hodnotě, je vyhledávání úspěšné.
5. Pokud je prostřední prvek větší než cíl, hledejte v levé polovině rozsahu.
6. Pokud je prostřední prvek menší než cíl, hledejte v pravé polovině rozsahu.
7. Opakujte kroky 2–6, dokud nenaleznete cílový prvek nebo dokud nebude rozsah hledání prázdný.

Příklad

Uvažujme seřazený seznam celých čísel a chceme najít číslo 34 pomocí binárního vyhledávání.

Seřazený seznam: {12, 23, 34, 45, 56, 67, 89, 90}

1. Začněte s celým seznamem.
2. Střední prvek: 56(pozice 4). Porovnejte s 34.
3. 56 je větší než 34. Hledejte v levé polovině.
4. Nový střední prvek: 23(pozice 1). Porovnejte s 34.
5. 23 je menší než 34. Hledejte v pravé polovině.
6. Nový střední prvek: 45(pozice 3). Porovnejte s 34.
7. 45 je větší než 34. Hledejte v levé polovině.
8. Nový střední prvek: 34(pozice 2). Cíl nalezen.

Příklad kódu v 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;  
}  

V uvedeném příkladu binarySearch je funkce použita k nalezení čísla 34 v seřazeném seznamu celých čísel. Výsledkem bude pozice 34 v seznamu(pozice začínají od 0) nebo -1, pokud číslo nebude nalezeno.