Algorithm ya Utafutaji wa Binary (Binary Search) katika C++- Maelezo, Mfano, na Msimbo

Kanuni ya utafutaji wa binary ni njia bora zaidi ya kutafuta kipengele maalum katika orodha iliyopangwa. Tofauti na utafutaji wa mstari, ambao hukagua vipengele kwa kufuatana, utafutaji wa binary hugawanya orodha katika nusu na kulinganisha kipengele lengwa na kipengele cha kati. Utaratibu huu unarudiwa hadi kipengele kinacholengwa kipatikane au safu ya utafutaji inakuwa tupu.

Inavyofanya kazi

1. Anza na orodha nzima iliyopangwa.
2. Tafuta kipengele cha kati cha safu ya utafutaji ya sasa.
3. Linganisha kipengele cha kati na thamani inayolengwa.
4. Ikiwa kipengele cha kati ni sawa na thamani inayolengwa, utafutaji unafanikiwa.
5. Ikiwa kipengele cha kati ni kikubwa kuliko lengo, tafuta katika nusu ya kushoto ya masafa.
6. Ikiwa kipengele cha kati ni kidogo kuliko lengo, tafuta katika nusu ya kulia ya masafa.
7. Rudia hatua 2-6 hadi kipengele lengwa kipatikane au safu ya utafutaji iwe tupu.

Mfano

Hebu tuchunguze orodha iliyopangwa ya nambari kamili na tunataka kupata nambari 34 kwa kutumia utaftaji wa binary.

Orodha Iliyopangwa: {12, 23, 34, 45, 56, 67, 89, 90}

1. Anza na orodha nzima.
2. Kipengele cha kati: 56(nafasi 4). Linganisha na 34.
3. 56 ni kubwa kuliko 34. Tafuta katika nusu ya kushoto.
4. Kipengele kipya cha kati: 23(nafasi 1). Linganisha na 34.
5. 23 ni ndogo kuliko 34. Tafuta katika nusu ya kulia.
6. Kipengele kipya cha kati: 45(nafasi 3). Linganisha na 34.
7. 45 ni kubwa kuliko 34. Tafuta katika nusu ya kushoto.
8. Kipengele kipya cha kati: 34(nafasi 2). Lengo limepatikana.

Msimbo wa Mfano katika 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;  
}  

Katika mfano uliotolewa, binarySearch chaguo la kukokotoa linatumika kupata nambari 34 katika orodha iliyopangwa ya nambari kamili. Matokeo yatakuwa nafasi ya 34 kwenye orodha(nafasi zinaanzia 0) au -1 ikiwa nambari haipatikani.