close

Dvejetainis paieškos (Binary Search) algoritmas C++ – paaiškinimas, pavyzdys ir kodas

Dvejetainis paieškos algoritmas yra efektyvesnis būdas ieškoti konkretaus elemento surūšiuotame sąraše. Skirtingai nuo linijinės paieškos, kuri elementus tikrina nuosekliai, dvejetainė paieška padalija sąrašą į dalis ir lygina tikslinį elementą su viduriniu elementu. Šis procesas kartojamas tol, kol randamas tikslinis elementas arba paieškos diapazonas tampa tuščias.

Kaip tai veikia

  1. Pradėkite nuo viso surūšiuoto sąrašo.
  2. Raskite vidurinį dabartinio paieškos diapazono elementą.
  3. Palyginkite vidurinį elementą su tiksline reikšme.
  4. Jei vidurinis elementas yra lygus tikslinei reikšmei, paieška sėkminga.
  5. Jei vidurinis elementas yra didesnis už tikslą, ieškokite kairėje diapazono pusėje.
  6. Jei vidurinis elementas yra mažesnis už tikslą, ieškokite dešinėje diapazono pusėje.
  7. Kartokite 2–6 veiksmus, kol bus rastas tikslinis elementas arba paieškos diapazonas taps tuščias.

Pavyzdys

Panagrinėkime surūšiuotą sveikųjų skaičių sąrašą ir norime rasti skaičių 34 naudodami dvejetainę paiešką.

Surūšiuotas sąrašas: {12, 23, 34, 45, 56, 67, 89, 90}

  1. Pradėkite nuo viso sąrašo.
  2. Vidurinis elementas: 56(4 padėtis). Palyginkite su 34.
  3. 56 yra didesnis nei 34. Ieškokite kairėje pusėje.
  4. Naujas vidurinis elementas: 23(1 padėtis). Palyginkite su 34.
  5. 23 yra mažesnis nei 34. Ieškokite dešinėje pusėje.
  6. Naujas vidurinis elementas: 45(3 padėtis). Palyginkite su 34.
  7. 45 yra didesnis nei 34. Ieškokite kairėje pusėje.
  8. Naujas vidurinis elementas: 34(2 padėtis). Taikinys rastas.

Kodo pavyzdys 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;  
}

Pateiktame pavyzdyje binarySearch funkcija naudojama norint rasti skaičių 34 surūšiuotame sveikųjų skaičių sąraše. Rezultatas bus 34 pozicija sąraše(pozicijos prasideda nuo 0) arba -1, jei skaičius nerastas.