close

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 নম্বর পাওয়া না গেলে।