(Binary Search) C++లో బైనరీ శోధన అల్గోరిథం- వివరణ, ఉదాహరణ మరియు కోడ్

బైనరీ శోధన అల్గోరిథం అనేది క్రమబద్ధీకరించబడిన జాబితాలో నిర్దిష్ట మూలకం కోసం శోధించడానికి మరింత సమర్థవంతమైన మార్గం. లీనియర్ శోధన వలె కాకుండా, మూలకాలను వరుసగా తనిఖీ చేస్తుంది, బైనరీ శోధన జాబితాను సగభాగాలుగా విభజిస్తుంది మరియు లక్ష్య మూలకాన్ని మధ్య మూలకంతో పోలుస్తుంది. లక్ష్య మూలకం కనుగొనబడే వరకు లేదా శోధన పరిధి ఖాళీ అయ్యే వరకు ఈ ప్రక్రియ పునరావృతమవుతుంది.

అది ఎలా పని చేస్తుంది

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 అవుతుంది.