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۔