একটি ইউনিক পূর্ণসংখ্যা অ্যারে দেওয়া আছে। স্ট্যান্ডার্ড বাইনারি সার্চ ব্যবহার করে কতগুলো উপাদান সফলভাবে খুঁজে বের করা যায় তা গণনা করুন। অ্যারে সর্টেড নাও হতে পারে।
উদাহরণ
ইনপুট: [2, 6, 4, 3, 10]
আউটপুট: 3
ব্যাখ্যা: ৪ (মিডল), ২ (লেফ্ট), ১০ (রাইট) - এই তিনটি বাইনারি সার্চে পাওয়া যায়।
অ্যালগরিদম
- প্রতিটি উপাদানের জন্য বাইনারি সার্চ চালান।
- সফল হলে কাউন্ট বাড়ান।
- মোট কাউন্ট ফেরত দিন।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool help(int target, vector<int>& nums) {
int low = 0, high = nums.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) return true;
if (nums[mid] < target) low = mid + 1;
else high = mid - 1;
}
return false;
}
int solve(vector<int>& nums) {
int ret = 0;
for (int x : nums)
ret += help(x, nums);
return ret;
}
};
int main() {
Solution ob;
vector<int> v = {2, 6, 4, 3, 10};
cout << ob.solve(v);
return 0;
}
মূল বিষয়
অ্যারে অনসর্টেড থাকলেও বাইনারি সার্চ চলে, কিন্তু সব উপাদান পাওয়া যায় না। যেসব উপাদান "সঠিক পথে" পড়ে, শুধু সেগুলো পাওয়া যায়। সময় জটিলতা: O(n log n)।
