বাইনারি সার্চ (Binary Search) একটি সার্চ অ্যালগরিদম যা সর্টেড অ্যারে-এ টার্গেট ভ্যালুর পজিশন খুঁজে বের করে। এটি টার্গেট ভ্যালutako মাঝপথের উপাদানের সাথে তুলনা করে। টাইম কমপ্লেক্সিটি O(log n)। (মূল আর্টিকেলে O(1) ভুল লেখা আছে)।
প্রধান STL ফাংশনগুলো:
- binary_search(first, last, val) – ভ্যালু পাওয়া গেলে
true, নাহলেfalseরিটার্ন করে। - lower_bound(first, last, val) – ভ্যালু যদি থাকে তবে প্রথম occurrence-এর পজিশন, না থাকলে ভ্যালুর চেয়ে বড় পরবর্তী উপাদানের পজিশন রিটার্ন করে।
- upper_bound(first, last, val) – ভ্যালু যদি থাকে তবে শেষ occurrence-এর পরের পজিশন, না থাকলে ভ্যালুর চেয়ে বড় পরবর্তী উপাদানের পজিশন রিটার্ন করে।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {6, 7, 10, 14, 16, 20}; // সর্টেড থাকতে হবে
// binary_search
if (binary_search(a.begin(), a.end(), 50))
cout << "50 exists in vector";
else
cout << "50 does not exist";
cout << endl;
if (binary_search(a.begin(), a.end(), 7))
cout << "7 exists in the vector";
else
cout << "7 does not exist";
cout << endl;
// lower_bound: 7-এর প্রথম পজিশন (ইন্ডেক্স ১)
cout << "The position of 7 using lower_bound: ";
cout << lower_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
// upper_bound: 7-এর শেষ পজিশনের পরের পজিশন (ইন্ডেক্স ২)
cout << "The position of 7 using upper_bound: ";
cout << upper_bound(a.begin(), a.end(), 7) - a.begin();
cout << endl;
return 0;
}
আউটপুট
50 does not exist 7 exists in the vector The position of 7 using lower_bound: 1 The position of 7 using upper_bound: 2
ব্যবহারিক টিপস:
lower_boundএবংupper_boundএর পার্থক্য: একই ভ্যালুর একাধিক কপি থাকলেlower_boundপ্রথমটিকে,upper_boundশেষটির পরের পজিশন দেয়।- এই ফাংশনগুলো যেকোনো র্যান্ডম-অ্যাক্সেস ইটারেটর সাথে কাজ করে (vector, array, deque, string)।
equal_rangeদিয়ে একসাথেlower_boundওupper_boundপাওয়া যায়।
