C++ में संयोग खोज (Coincidence Search)

मान लीजिए हमारे पास अद्वितीय पूर्णांकों की एक सूची nums है। हमें उन पूर्णांकों की संख्या ज्ञात करनी है जिन्हें मानक बाइनरी खोज का उपयोग करके सफलतापूर्वक खोजा जा सकता है।

उदाहरण के लिए, यदि इनपुट है [2, 6, 4, 3, 10], तो आउटपुट 3 होगा, क्योंकि यदि हम 4 को खोजने के लिए बाइनरी खोज का उपयोग करते हैं, तो हम इसे पहली पुनरावृत्ति में पा सकते हैं। हम 2 और 10 को दो पुनरावृत्तियों के बाद भी पा सकते हैं।

समाधान दृष्टिकोण

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

एक फ़ंक्शन help() परिभाषित करें जो target और सरणी nums लेता है।
- low := 0
- high := nums का आकार - 1
- while low <= high:
  - mid := low + (high - low) / 2
  - यदि nums[mid] == target, तो true लौटाएं
  - यदि nums[mid] < target, तो low := mid + 1
  - अन्यथा high := mid - 1
- false लौटाएं
मुख्य विधि से:
- ret := 0
- nums में प्रत्येक तत्व i के लिए:
  - ret := ret + help(i, nums)
- ret लौटाएं

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool help(int target, vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target)
                return true;
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return false;
    }
    
    int solve(vector<int>& nums) {
        int ret = 0;
        for (int i : nums) {
            ret += help(i, nums);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2, 6, 4, 3, 10};
    cout << (ob.solve(v));
    return 0;
}

इनपुट

{2, 6, 4, 3, 10}