অজানা সাইজের সর্টেড অ্যারে فيها সার্চ C++-এ

সমস্যা বিবরণ

একটি সর্টেড অ্যারে আছে কিন্তু এর সাইজ অজানা। শুধু ArrayReader.get(k) কল করে индекс k-এлемен্ট পাওয়া যায়। একটি টার্গেট ভ্যালু দেওয়া আছে, সেটি খুঁজে বের করুন। পাওয়া গেলে ইন্ডেক্স রিটার্ন করুন, না পেলে -1।

উদাহরণ

অ্যারে = [-1,0,3,5,9,12], টার্গেট = 9

আউটপুট: 4 (ইন্ডেক্স ৪-এ ৯ আছে)

অ্যালগরিদম: এক্সপোনেনশিয়াল সার্চ + বাইনারি সার্চ

1. বাউন্ড খুঁজুন: high = 1 থেকে শুরু করে reader.get(high) < target থাকা পর্যন্ত high *= 2 করুন। low = high/2।
2. বাইনারি সার্চ: [low, high] রেঞ্জে সাধারণ বাইনারি সার্চ করুন।
3. পাওয়া গেলে ইন্ডেক্স রিটার্ন, না পেলে -1।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

class ArrayReader {
    vector<int> v;
public:
    ArrayReader(vector<int>& v) : v(v) {}
    int get(int i) { return v[i]; }
};

class Solution {
public:
    int search(ArrayReader& reader, int target) {
        int low = 0, high = 1;
        while (reader.get(high) < target) {
            low = high;
            high <<= 1; // high *= 2
        }
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int x = reader.get(mid);
            if (x == target) return mid;
            if (x > target) high = mid - 1;
            else low = mid + 1;
        }
        return -1;
    }
};

int main() {
    Solution ob;
    vector<int> v = {-1,0,3,5,9,12};
    ArrayReader reader(v);
    cout << ob.search(reader, 9); // আউটপুট: 4
    return 0;
}

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(log T) — T = টার্গেটের ইন্ডেক্স। এক্সপোনেনশিয়াল সার্চ O(log T), বাইনারি সার্চ O(log T)।
• স্থান জটিলতা: O(1)।