বাইনারী সার্চ হল একটি সার্চ অ্যালগরিদম যা অ্যারের মধ্যম মানের সাথে তুলনা করে এবং মানের উপর ভিত্তি করে এটিকে ভাগ করে একটি উপাদান অনুসন্ধান করে। উপাদানটি না পাওয়া পর্যন্ত অ্যালগরিদম বারবার এটি করে।
এটিতে একটি বাইনারি অনুসন্ধান প্রয়োগ করার জন্য অ্যারেটি সাজানো উচিত।
বাইনারি অনুসন্ধানের সময় জটিলতা হল লগারিদমিক আদেশ এই কারণেই প্রোগ্রামারদের জন্য অ্যালগরিদম কোড করার সময় কমাতে বাইনারি অনুসন্ধানের সাথে এর বাস্তবায়নের সাথে সম্পর্কিত শর্টহ্যান্ডগুলিও জানা খুবই গুরুত্বপূর্ণ। স্ট্যান্ডার্ড টেমপ্লেট লাইব্রেরিতে (STL) অন্তর্ভুক্ত বাইনারি অনুসন্ধান অ্যালগরিদমের সাথে সম্পর্কিত ফাংশনগুলি এখানে আলোচনা করা হয়েছে৷
নিম্ন_সীমা − নিম্ন আবদ্ধ অনুসন্ধানটি সেই অবস্থানটি প্রদান করে যেখানে উপাদানটি পাওয়া যায়।
সিনট্যাক্স
lower_bound(start_pointer , end_pointer, element )
এখানে,
start_pointer পয়েন্টার যা সার্চ স্ট্রাকচারের প্রারম্ভিক বিন্দুর মেমরি অবস্থান ধরে রাখে।
end_pointer একটি পয়েন্টার যা সার্চ স্ট্রাকচারের এন্ডপয়েন্টের মেমরি অবস্থান ধরে রাখে।
উপাদান ফাংশন ব্যবহার করে পাওয়া যায় এমন উপাদান।
ফাংশনটি উপাদানটির সূচী প্রদান করে যা পাওয়া যাবে।
ফেরত মান একাধিক মান নিতে পারে −
যদি উপাদানটি গঠনে একবার আসে, তাহলে অবস্থানটি ফেরত দেওয়া হয়।
যদি উপাদানটি কাঠামোতে একাধিকবার ঘটে, তবে প্রথম উপাদানটির অবস্থান ফেরত দেওয়া হয়।
যদি উপাদানটি গঠনে না ঘটে, তাহলে একটি উপাদানের চেয়ে পরবর্তী উচ্চ সংখ্যার অবস্থান ফেরত দেওয়া হয়।
সূচক কাঠামোর ভিত্তি অবস্থান বিয়োগ করে যে কোনো উপাদানের পাওয়া যায়।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> sortedarray = {2 , 5, 7, 8 , 15, 20 };
vector<int> sortedarray2 = {2, 3, 4, 6 , 9 , 23 };
vector<int> sortedarray3 = {2 , 5, 7, 7 , 15, 20 };
cout<<"The position of element 7 found using lower_bound function :";
cout<<"\nCase 1 : When element is present in array but only once ";
cout<<lower_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
cout<<"\nCase 2 : When element is present more than one times in the array ";
cout<<lower_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
cout<<"\nCase 3 : When element is not present in the array ";
cout<<lower_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
} আউটপুট
The position of element 7 found using lower_bound function : Case 1 : When element is present in array but only once 2 Case 2 : When element is present more than one times in the array 2 Case 3 : When element is not present in the array 4
উর্ধ্ব_সীমা − উপরের আবদ্ধ অনুসন্ধানটি উপাদানটির অবস্থান প্রদান করে যা পাস করা উপাদানের চেয়ে বেশি৷
সিনট্যাক্স
upper_bound(start_pointer , end_pointer, element)
এখানে,
start_pointer পয়েন্টার যা সার্চ স্ট্রাকচারের প্রারম্ভিক বিন্দুর মেমরি অবস্থান ধরে রাখে।
end_pointer একটি পয়েন্টার যা সার্চ স্ট্রাকচারের এন্ডপয়েন্টের মেমরি অবস্থান ধরে রাখে।
উপাদান ফাংশন ব্যবহার করে পাওয়া যায় এমন উপাদান।
ফাংশনটি সেই উপাদানটির সূচী প্রদান করে যার মান উপাদানটির মানের থেকে বেশি৷
ফেরত মান একাধিক মান নিতে পারে −
যদি উপাদানটি গঠনে একবার আসে, তাহলে পরবর্তী উচ্চতর উপাদানটি ফেরত দেওয়া হয়।
যদি উপাদানটি কাঠামোতে একাধিকবার ঘটে, তবে শেষ উপাদানটির পরবর্তী উপাদানটির অবস্থান ফেরত দেওয়া হয়।
যদি উপাদানটি গঠনে না ঘটে, তাহলে উপাদানটির চেয়ে পরবর্তী উচ্চ সংখ্যার অবস্থান ফেরত দেওয়া হয়।
সূচক কাঠামোর ভিত্তি অবস্থান বিয়োগ করে যে কোনো উপাদানের পাওয়া যায়।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> sortedarray = {2 , 5, 7, 8 , 15, 20 };
vector<int> sortedarray2 = {2, 3, 4, 6 , 9 , 23 };
vector<int> sortedarray3 = {2 , 5, 7, 7 , 15, 20 };
cout<<"The position of element 7 found using upper_bound function :";
cout<<"\nCase 1 : When element is present in array but only once ";
cout<<upper_bound(sortedarray.begin() , sortedarray.end(), 7) - sortedarray.begin();
cout<<"\nCase 2 : When element is present more than one times in the array ";
cout<<upper_bound(sortedarray3.begin() , sortedarray3.end(), 7) - sortedarray3.begin();
cout<<"\nCase 3 : When element is not present in the array ";
cout<<upper_bound(sortedarray2.begin() , sortedarray2.end(), 7) - sortedarray2.begin();
} আউটপুট
The position of element 7 found using upper_bound function : Case 1 : When element is present in array but only once 3 Case 2 : When element is present more than one times in the array 4 Case 3 : When element is not present in the array 4
বাইনারী_সার্চ একটি ফাংশন যা উপাদানটি কাঠামোতে উপস্থিত আছে কিনা তা পরীক্ষা করে।
সিনট্যাক্স
binary_search(start_pointer , end_pointer, element)
এখানে,
start_pointer পয়েন্টার যা সার্চ স্ট্রাকচারের প্রারম্ভিক বিন্দুর মেমরি অবস্থান ধরে রাখে।
end_pointer একটি পয়েন্টার যা সার্চ স্ট্রাকচারের এন্ডপয়েন্টের মেমরি অবস্থান ধরে রাখে।
উপাদান ফাংশন ব্যবহার করে পাওয়া যায় এমন উপাদান।
যদি উপাদানটি কাঠামোতে উপস্থিত থাকে, ফাংশনটি সত্যে ফিরে আসে। অন্যথায়, এটি মিথ্যা ফিরে আসবে৷
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> sortedarray = {6, 15, 21, 27, 39, 42};
cout<<"The element to be found in the array is 21\n" ;
if(binary_search(sortedarray.begin(), sortedarray.end(), 21))
cout<<"The element is found";
else
cout<<"The element is not found";
cout<<"\nThe element to be found in the array is 5\n" ;
if(binary_search(sortedarray.begin(), sortedarray.end(), 5))
cout<<"The element is found";
else
cout<<"The element is not found";
} আউটপুট
The element to be found in the array is 21 The element is found The element to be found in the array is 5 The element is not found
