C++ में अज्ञात आकार के क्रमबद्ध सरणी में खोजें

मान लीजिए कि हमारे पास एक सरणी है और इसे आरोही क्रम में क्रमबद्ध किया गया है, हमें अंकों में लक्ष्य खोजने के लिए एक फ़ंक्शन को परिभाषित करना होगा। यदि लक्ष्य मौजूद है, तो उसकी अनुक्रमणिका लौटाएं, अन्यथा -1 लौटाएं।

सरणी आकार ज्ञात नहीं है। हम केवल ArrayReader इंटरफ़ेस का उपयोग करके सरणी तक पहुँच सकते हैं। ArrayReader.get(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