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 ஆக இருக்கும்.