বাইনারি অনুসন্ধান হল একটি সাজানো অ্যারেতে প্রয়োজনীয় উপাদান খুঁজে বারবার অ্যারেকে অর্ধেক করে এবং অর্ধেকে অনুসন্ধান করার একটি পদ্ধতি৷
এই পদ্ধতিটি পুরো অ্যারে দিয়ে শুরু করে করা হয়। তারপর অর্ধেক করা হয়। যদি প্রয়োজনীয় ডেটা মান অ্যারের মাঝখানে উপাদানের চেয়ে বেশি হয়, তাহলে অ্যারের উপরের অর্ধেক বিবেচনা করা হয়। অন্যথায়, নিম্ন অর্ধেক বিবেচনা করা হয়। প্রয়োজনীয় ডেটা মান প্রাপ্ত না হওয়া বা অবশিষ্ট অ্যারে খালি না হওয়া পর্যন্ত এটি ক্রমাগত করা হয়৷
একটি প্রোগ্রাম যা C++ এ বাইনারি অনুসন্ধান প্রদর্শন করে তা নিচে দেওয়া হল।
উদাহরণ
#include
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 numberto search 20 20 is present at index 5 in the array
উপরের প্রোগ্রামে, binarySearch() একটি পুনরাবৃত্ত ফাংশন যা বাইনারি অনুসন্ধান ব্যবহার করে অ্যারেতে প্রয়োজনীয় উপাদান খুঁজে পেতে ব্যবহৃত হয়। ফাংশনটি অ্যারে, এর নিম্ন সীমা এবং উপরের সীমানা এবং সেইসাথে পরামিতি হিসাবে পাওয়া সংখ্যা নেয়। এটি নীচে দেখানো হয়েছে৷
৷int binarySearch(int arr[], int p, int r, int num)
তারপর অ্যারের মধ্যবিন্দু গণনা করা হয়। যদি মধ্যবিন্দুতে মানটি সংখ্যার সমান হয়, তবে এটি ফেরত দেওয়া হবে। যদি মানটি num-এর থেকে বেশি হয়, তাহলে অ্যারে লোয়ার বাউন্ড p এবং আপার বাউন্ড মিড-1 এর সাথে রিকার্সিভলি কল করে। যদি মানটি num-এর থেকে কম হয়, তাহলে অ্যারে লোয়ার বাউন্ড মিড+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() দ্বারা প্রত্যাবর্তিত মান -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;
} 