ধরুন আমাদের একটি অ্যারে আছে এবং সেটি ক্রমবর্ধমান ক্রমে সাজানো হয়েছে, আমাদেরকে সংখ্যায় লক্ষ্য অনুসন্ধানের জন্য একটি ফাংশন সংজ্ঞায়িত করতে হবে। যদি লক্ষ্য উপস্থিত থাকে, তাহলে তার সূচকটি ফেরত দিন, অন্যথায়, -1 ফেরত দিন।
অ্যারের আকার জানা নেই। আমরা শুধুমাত্র একটি ArrayReader ইন্টারফেস ব্যবহার করে অ্যারে অ্যাক্সেস করতে পারি। এখানে একটি গেট ফাংশন আছে যেমন ArrayReader.get(k) এটি সূচী k-এ অ্যারের উপাদান ফিরিয়ে দেবে।
সুতরাং, যদি ইনপুটটি অ্যারে =[-1,0,3,5,9,12], লক্ষ্য =9 এর মত হয়, তাহলে আউটপুট 4 হবে কারণ 9 সংখ্যায় বিদ্যমান এবং এর সূচক 4
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
উচ্চ :=1, নিম্ন :=0
-
যখন পাঠক <টার্গেট, ডু −
পাওয়ার(উচ্চ)-
নিম্ন :=উচ্চ
-
উচ্চ =উচ্চ * 2
-
-
যখন কম <=উচ্চ, করুন −
-
মধ্য :=নিম্ন + (উচ্চ - নিম্ন) / 2
-
x :=পাঠকের (মাঝামাঝি) পাওয়া
-
যদি x টার্গেটের সমান হয়, তাহলে −
-
মাঝামাঝি ফেরত
-
-
যদি x> টার্গেট হয়, তাহলে −
-
উচ্চ :=মধ্য - 1
-
-
অন্যথায়
-
নিম্ন :=মধ্য + 1
-
-
-
রিটার্ন -1
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class ArrayReader{
private:
vector<int> v;
public:
ArrayReader(vector<int> &v){
this->v = v;
}
int get(int i){
return v[i];
}
};
class Solution {
public:
int search(ArrayReader& reader, int target) {
int high = 1;
int low = 0;
while (reader.get(high) < target) {
low = high;
high <<= 1;
}
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;
}
};
main(){
Solution ob;
vector<int> v = {-1,0,3,5,9,12};
ArrayReader reader(v);
cout<<(ob.search(reader, 9));
} ইনপুট
{-1,0,3,5,9,12}, 9 আউটপুট
4
