close

Algoritmi i Kërkimit Binar (Binary Search) në C++- Shpjegim, Shembull dhe Kodi

Algoritmi binar i kërkimit është një mënyrë më efikase për të kërkuar një element specifik në një listë të renditur. Ndryshe nga kërkimi linear, i cili kontrollon elementët në mënyrë sekuenciale, kërkimi binar e ndan listën në gjysma dhe krahason elementin e synuar me elementin e mesëm. Ky proces përsëritet derisa të gjendet elementi i synuar ose të zbrazet diapazoni i kërkimit.

Si punon

  1. Filloni me të gjithë listën e renditur.
  2. Gjeni elementin e mesëm të gamës aktuale të kërkimit.
  3. Krahasoni elementin e mesëm me vlerën e synuar.
  4. Nëse elementi i mesëm është i barabartë me vlerën e synuar, kërkimi është i suksesshëm.
  5. Nëse elementi i mesëm është më i madh se objektivi, kërkoni në gjysmën e majtë të diapazonit.
  6. Nëse elementi i mesëm është më i vogël se objektivi, kërkoni në gjysmën e djathtë të diapazonit.
  7. Përsëritni hapat 2-6 derisa të gjendet elementi i synuar ose diapazoni i kërkimit të bëhet bosh.

Shembull

Le të shqyrtojmë një listë të renditur të numrave të plotë dhe duam të gjejmë numrin 34 duke përdorur kërkimin binar.

Lista e renditur: {12, 23, 34, 45, 56, 67, 89, 90}

  1. Filloni me të gjithë listën.
  2. Elementi i mesëm: 56(pozicioni 4). Krahaso me 34.
  3. 56 është më i madh se 34. Kërkoni në gjysmën e majtë.
  4. Element i ri i mesëm: 23(pozicioni 1). Krahaso me 34.
  5. 23 është më i vogël se 34. Kërko në gjysmën e djathtë.
  6. Elementi i mesëm i ri: 45(pozicioni 3). Krahaso me 34.
  7. 45 është më i madh se 34. Kërkoni në gjysmën e majtë.
  8. Elementi i mesëm i ri: 34(pozicioni 2). Objektivi u gjet.

Shembull Kodi në 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;  
}

Në shembullin e dhënë, binarySearch funksioni përdoret për të gjetur numrin 34 në një listë të renditur të numrave të plotë. Rezultati do të jetë pozicioni 34 në listë(pozicionet fillojnë nga 0) ose -1 nëse numri nuk gjendet.