मान लीजिए हमारे पास एक सरणी है जो आरोही क्रम में सॉर्टेड है, हमें nums में लक्ष्य को खोजने के लिए एक फ़ंक्शन परिभाषित करना है। यदि लक्ष्य मौजूद है, तो उसका इंडेक्स लौटाएं, अन्यथा -1 लौटाएं।
सरणी का आकार ज्ञात नहीं है। हम केवल ArrayReader इंटरफ़ेस का उपयोग करके सरणी तक पहुंच सकते हैं। एक get फ़ंक्शन है जैसे ArrayReader.get(k) जो इंडेक्स k पर सरणी का तत्व लौटाता है।
उदाहरण के लिए, यदि इनपुट सरणी = [-1,0,3,5,9,12], लक्ष्य = 9 है, तो आउटपुट 4 होगा क्योंकि 9 nums में मौजूद है और इसका इंडेक्स 4 है।
हल करने की विधि
हम घातांकीय खोज और बाइनरी खोज का उपयोग करेंगे:
- high = 1, low = 0 प्रारंभ करें।
- जब तक reader.get(high) < लक्ष्य: low = high, high = high * 2।
- फिर मानक बाइनरी खोज करें low से high तक।
- यदि मिला तो इंडेक्स लौटाएं, अन्यथा -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
