C++ માં બાઈનરી સર્ચ (Binary Search) અલ્ગોરિધમ- સમજૂતી, ઉદાહરણ અને કોડ

દ્વિસંગી શોધ અલ્ગોરિધમ એ સૉર્ટ કરેલ સૂચિમાં ચોક્કસ તત્વ શોધવાની વધુ કાર્યક્ષમ રીત છે. રેખીય શોધથી વિપરીત, જે તત્વોને ક્રમિક રીતે તપાસે છે, દ્વિસંગી શોધ સૂચિને અર્ધભાગમાં વહેંચે છે અને લક્ષ્ય તત્વની મધ્યમ તત્વ સાથે સરખામણી કરે છે. જ્યાં સુધી લક્ષ્ય તત્વ ન મળે અથવા શોધ શ્રેણી ખાલી ન થાય ત્યાં સુધી આ પ્રક્રિયાનું પુનરાવર્તન થાય છે.

તે કેવી રીતે કામ કરે છે

1. સંપૂર્ણ સૉર્ટ કરેલી સૂચિથી પ્રારંભ કરો.
2. વર્તમાન શોધ શ્રેણીનું મધ્યમ તત્વ શોધો.
3. લક્ષ્ય મૂલ્ય સાથે મધ્યમ તત્વની તુલના કરો.
4. જો મધ્યમ તત્વ લક્ષ્ય મૂલ્યની બરાબર હોય, તો શોધ સફળ થાય છે.
5. જો મધ્યમ તત્વ લક્ષ્ય કરતા વધારે હોય, તો શ્રેણીના ડાબા અડધા ભાગમાં શોધો.
6. જો મધ્યમ તત્વ લક્ષ્ય કરતાં નાનું હોય, તો શ્રેણીના જમણા અડધા ભાગમાં શોધો.
7. જ્યાં સુધી લક્ષ્ય તત્વ ન મળે અથવા શોધ શ્રેણી ખાલી ન થાય ત્યાં સુધી પગલાં 2-6નું પુનરાવર્તન કરો.

ઉદાહરણ

ચાલો પૂર્ણાંકોની સૉર્ટ કરેલી સૂચિને ધ્યાનમાં લઈએ અને દ્વિસંગી શોધનો ઉપયોગ કરીને 34 નંબર શોધવા માંગીએ છીએ.

સૉર્ટ કરેલ સૂચિ: {12, 23, 34, 45, 56, 67, 89, 90}

1. સંપૂર્ણ સૂચિ સાથે પ્રારંભ કરો.
2. મધ્ય તત્વ: 56(સ્થિતિ 4). 34 સાથે સરખામણી કરો.
3. 56 34 કરતા વધારે છે. ડાબા ભાગમાં શોધો.
4. નવું મધ્યમ તત્વ: 23(સ્થિતિ 1). 34 સાથે સરખામણી કરો.
5. 23 34 કરતા નાનું છે. જમણા અડધા ભાગમાં શોધો.
6. નવું મધ્યમ તત્વ: 45(પોઝિશન 3). 34 સાથે સરખામણી કરો.
7. 45 એ 34 કરતા વધારે છે. ડાબા અડધા ભાગમાં શોધો.
8. નવું મધ્યમ તત્વ: 34(સ્થિતિ 2). લક્ષ્ય મળ્યું.

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

આપેલ ઉદાહરણમાં, binarySearch ફંક્શનનો ઉપયોગ પૂર્ણાંકોની સૉર્ટ કરેલી સૂચિમાં નંબર 34 શોધવા માટે થાય છે. પરિણામ યાદીમાં 34 ની સ્થિતિ હશે(પોઝિશન 0 થી શરૂ થાય છે) અથવા -1 જો નંબર ન મળે તો.