सी++ में खोज इंसर्ट पोजीशन

मान लीजिए कि हमारे पास एक क्रमबद्ध सरणी गिरफ्तारी और लक्ष्य मान है, तो लक्ष्य मिलने पर हमें अनुक्रमणिका ढूंढनी होगी। यदि वह मौजूद नहीं है, तो उस अनुक्रमणिका को वापस कर दें जहां यह होगा यदि इसे क्रम में डाला गया था।

इसलिए, यदि इनपुट [1,3,4,6,6] और लक्ष्य =5 जैसा है, तो आउटपुट 3 होगा, क्योंकि हम इंडेक्स 3 पर 5 सम्मिलित कर सकते हैं, इसलिए सरणी [1,3] होगी 4,5,6,6]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे-

• n :=A का आकार

• यदि n <1, तो -

  • वापसी 0

• निम्न :=0, उच्च :=n - 1

• जबकि कम <=उच्च, करें −

  • मध्य :=निम्न + (उच्च-निम्न) /2

  • यदि A[मध्य] लक्ष्य के समान है, तो -

    • बीच में लौटें

  • अन्यथा जब A[mid]> लक्ष्य, तब −

    • उच्च:=मध्य -1, स्थिति:=मध्य

  • अन्यथा

    • निम्न:=मध्य + 1, स्थिति:=मध्य + 1

• वापसी स्थिति

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int searchInsert(vector<int>& A, int target) {
      int n = A.size();
      if(n < 1) {
         return 0;
      }
      int low = 0;
      int high = n-1;
      int mid;
      int pos;
      while(low <= high) {
         mid = low + (high-low)/2;
         if(A[mid] == target) {
            return mid;
         }
         else if(A[mid] > target) {
            high = mid - 1;
            pos = mid;
         }
         else {
            low = mid + 1;
            pos = mid + 1;
         }
      }
      return pos;
   }
};
main(){
   Solution ob;
   vector<int&g; v = {1,3,4,6,6};
   cout << (ob.searchInsert(v,5));
}

इनपुट

{1,3,4,6,6},5

आउटपुट

3