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

समस्या विवरण

मान लीजिए हमारे पास एक सॉर्टेड सरणी arr और एक लक्ष्य मान है, हमें वह इंडेक्स ढूंढना है जहां लक्ष्य पाया जाता है। यदि यह मौजूद नहीं है, तो वह इंडेक्स लौटाएं जहां इसे क्रम में डाला जाएगा।

उदाहरण

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

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (बाइनरी सर्च):

• n := A का आकार
• यदि n < 1, तो 0 लौटाएं
• low := 0, high := n - 1
• जब low <= high:
  • mid := low + (high - low) / 2
  • यदि A[mid], target के समान है:
    • mid लौटाएं
  • अन्यथा यदि A[mid] > target:
    • high := mid - 1, pos := mid
  • अन्यथा:
    • low := mid + 1, pos := mid + 1
• pos लौटाएं

C++ कार्यान्वयन

#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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,3,4,6,6};
    cout << (ob.searchInsert(v,5));
    return 0;
}

इनपुट

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

आउटपुट

3