C++-তে বাইনারি সার্চ

বাইনারি সার্চ হলো একটি সাজানো অ্যারেতে ضرুরী উপাদান খুঁজে বের করার একটি পদ্ধতি যা অ্যারেটি বারবার অর্ধেক করে এবং অর্ধেক অংশে সার্চ করে।

এই পদ্ধতিটি পুরো অ্যারেটি लेकर শুরু হয়। তারপর এটি অর্ধেক করা হয়। যদি ضرুরী ডেটা ভ্যালু অ্যারের মাঝপথে থাকা উপাদানের চেয়ে বড় হয়, তবে অ্যারের উপরের অর্ধেক অংশ বিবেচনা করা হয়। অন্যথায়, নিচের অর্ধেক অংশ বিবেচনা করা হয়। এটি তবদিয়া চলে যতক্ষণ না ضرুরী ডেটা ভ্যালু পাওয়া যায় অথবা অবশিষ্ট অ্যারেটি খালি হয়।

C++-তে বাইনারি সার্চ প্রদর্শন করে এমন একটি প্রোগ্রাম নিচে দেওয়া হলো:

উদাহরণ

#include <iostream>
using namespace std;

int binarySearch(int arr[], int p, int r, int num) {
    if (p <= r) {
        int mid = (p + r) / 2;
        if (arr[mid] == num)
            return mid;
        if (arr[mid] > num)
            return binarySearch(arr, p, mid - 1, num);
        if (arr[mid] < num)
            return binarySearch(arr, mid + 1, r, num);
    }
    return -1;
}

int main(void) {
    int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int num;
    cout << "Enter the number to search: \n";
    cin >> num;
    int index = binarySearch(arr, 0, n - 1, num);
    if (index == -1) {
        cout << num << " is not present in the array";
    } else {
        cout << num << " is present at index " << index << " in the array";
    }
    return 0;
}

আউটপুট

Enter the number to search: 20
20 is present at index 5 in the array

উপরোক্ত প্রোগ্রামে, binarySearch() একটি রিকারসিভ ফাংশন যা বাইনারি সার্চ ব্যবহার করে অ্যারেতে ضرুরী উপাদান খুঁজে বের করতে ব্যবহৃত হয়। ফাংশনটি অ্যারে, এর লোয়ার বাউন্ড এবং আপার বাউন্ডসহ খুঁজে বের করার সংখ্যাকে প্যারামিটার হিসেবে নেয়। এটি নিচে দেখানো হলো:

int binarySearch(int arr[], int p, int r, int num)

তারপর অ্যারের মিডপয়েন্ট গণনা করা হয়। যদি মিডপয়েন্টের মান num-এর সমান হয়, তবে সেটি রিটার্ন করা হয়। যদি মান num-এর চেয়ে বড় হয়, তবে অ্যারে নিজেকে রিকারসিভলি লোয়ার বাউন্ড p এবং আপার বাউন্ড mid-1 দিয়ে কল করে। যদি মান num-এর চেয়ে ছোট হয়, তবে অ্যারে নিজেকে রিকারসিভলি লোয়ার বাউন্ড mid+1 এবং আপার বাউন্ড r দিয়ে কল করে। এটি নিচের কোড স্নিপেটে দেখা যাচ্ছে:

int binarySearch(int arr[], int p, int r, int num) {
    if (p <= r) {
        int mid = (p + r) / 2;
        if (arr[mid] == num)
            return mid;
        if (arr[mid] > num)
            return binarySearch(arr, p, mid - 1, num);
        if (arr[mid] < num)
            return binarySearch(arr, mid + 1, r, num);
    }
    return -1;
}

main() ফাংশনে, অ্যারে arr[] সংজ্ঞায়িত করা হয়েছে। অ্যারের আকার গণনা করা হয়েছে এবং খুঁজে বের করার সংখ্যা নির্দিষ্ট করা হয়েছে। তারপর binarySearch() কল করা হয়েছে সংখ্যার ইনডেক্স খুঁজে বের করতে। যদি binarySearch()-এর রিটার্ন করা মান -1 হয়, তবে সংখ্যাটি অ্যারেতে নেই। অন্যথায়, ইনডেক্স ভ্যালু রিটার্ন করা হয়। এটি নিচে দেওয়া হলো:

int main(void) {
    int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int num = 33;
    int index = binarySearch(arr, 0, n - 1, num);
    if (index == -1)
        cout << num << " is not present in the array";
    else
        cout << num << " is present at index " << index << " in the array";
    return 0;
}