বাইনারি সার্চ হল একটি সার্চ অ্যালগরিদম যা অ্যারেতে মাঝপথের মান সাথে তুলনা করে এবং মান অনুযায়ী ভাগ করে উপাদান খুঁজে বের করে। অ্যালগরিদমটি উপাদানটি পাওয়া না হওয়া পর্যন্ত এই প্রক্রিয়া বারবার दुहरায়।
বাইনারি সার্চ প্রয়োগ করার জন্য অ্যারেটি সর্ট করা থাকতে হবে।
বাইনারি সার্চের টাইম কমপ্লেক্সিটি লগারিদমিক ক্রমের। তাই প্রোগ্রামারদের জন্য বাইনারি সার্চের সংক্ষিপ্ত রূপও জানা খুব জরুরি যাতে অ্যালগরিদম কোড করার সময় কমানো যায়। স্ট্যান্ডার্ড টেমপ্লেট লাইব্রেরি (STL)-এ বাইনারি সার্চ অ্যালগরিদমের সাথে সম্পর্কিত ফাংশনগুলো নিচে আলোচনা করা হলো।
lower_bound
লোয়ার বাউন্ড সার্চটি উপাদানটি যেখানে পাওয়া যায় সে পজিশন রিটার্ন করে।
সিনট্যাক্স
lower_bound(start_pointer, end_pointer, element)
- start_pointer হল সার্চ স্ট্রাকচারের শুরুয়ের মেমরি লোকেশন ধারণকারী পয়েন্টার।
- end_pointer হল সার্চ স্ট্রাকচারের শেষের মেমরি লোকেশন ধারণকারী পয়েন্টার।
- element হল ফাংশন ব্যবহার করে খুঁজে বের করার উপাদান।
ফাংশনটি খুঁজে বের করার উপাদানের ইন্ডেক্স রিটার্ন করে।
রিটার্ন মান নিম্নরূপ হতে পারে:
- যদি উপাদানটি স্ট্রাকচারে একবার থাকে, তবে তার পজিশন রিটার্ন করা হয়।
- যদি উপাদানটি একাধিকবার থাকে, তবে প্রথম উপাদানের পজিশন রিটার্ন করা হয়।
- যদি উপাদানটি স্ট্রাকচারে না থাকে, তবে উপাদানের চেয়ে বড় അടുത്ത সংখ্যার পজিশন রিটার্ন করা হয়।
যেকোনো উপাদানের ইন্ডেক্স স্ট্রাকচারের বেস পজিশন বিয়োগ করে পাওয়া যায়।
উদাহরণ
#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
আপার বাউন্ড সার্চটি পাস করা উপাদানের চেয়ে বড় উপাদানের পজিশন রিটার্ন করে।
সিনট্যাক্স
upper_bound(start_pointer, end_pointer, element)
- start_pointer হল সার্চ স্ট্রাকচারের শুরুয়ের মেমরি লোকেশন ধারণকারী পয়েন্টার।
- end_pointer হল সার্চ স্ট্রাকচারের শেষের মেমরি লোকেশন ধারণকারী পয়েন্টার।
- element হল ফাংশন ব্যবহার করে খুঁজে বের করার উপাদান।
ফাংশনটি উপাদানের মান থেকে বড় মান হিসেবে উপাদানের ইন্ডেক্স রিটার্ন করে।
রিটার্ন মান নিম্নরূপ হতে পারে:
- যদি উপাদানটি একবার থাকে, তবে পরবর্তী বড় উপাদানের পজিশন রিটার্ন করা হয়।
- যদি উপাদানটি একাধিকবার থাকে, তবে শেষ উপাদানের পরবর্তী উপাদানের পজিশন রিটার্ন করা হয়।
- যদি উপাদানটি স্ট্রাকচারে না থাকে, তবে উপাদানের চেয়ে বড় അടുത്ത সংখ্যার পজিশন রিটার্ন করা হয়।
যেকোনো উপাদানের ইন্ডেক্স স্ট্রাকচারের বেস পজিশন বিয়োগ করে পাওয়া যায়।
উদাহরণ
#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
binary_search হল একটি ফাংশন যা চেক করে উপাদানটি স্ট্রাকচারে আছে কিনা।
সিনট্যাক্স
binary_search(start_pointer, end_pointer, element)
- start_pointer হল সার্চ স্ট্রাকচারের শুরুয়ের মেমরি লোকেশন ধারণকারী পয়েন্টার।
- end_pointer হল সার্চ স্ট্রাকচারের শেষের মেমরি লোকেশন ধারণকারী পয়েন্টার।
- element হল ফাংশন ব্যবহার করে খুঁজে বের করার উপাদান।
যদি উপাদানটি স্ট্রাকচারে থাকে, ফাংশনটি true রিটার্ন করে। অন্যথায় false রিটার্ন করে।
উদাহরণ
#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
