मान लीजिए कि हमारे पास अद्वितीय पूर्णांकों की एक सूची है, जिन्हें अंक कहते हैं। हमें उन पूर्णांकों की संख्या ज्ञात करनी है जो अभी भी एक मानक बाइनरी खोज का उपयोग करके सफलतापूर्वक पाई जा सकती हैं।
तो, अगर इनपुट [2,6,4,3,10] जैसा है, तो आउटपुट 3 होगा, जैसे कि हम 4 को देखने के लिए बाइनरी सर्च का उपयोग करते हैं, हम इसे पहले पा सकते हैं पुनरावृत्ति हम दो पुनरावृत्तियों के बाद 2 और 10 भी ढूंढ सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन सहायता () को परिभाषित करें, यह लक्ष्य, एक सरणी और अंक लेगा,
-
कम :=0
-
उच्च :=अंकों का आकार - 1
-
जबकि कम <=उच्च, करें −
-
मध्य:=निम्न + (उच्च-निम्न)/2
-
यदि अंक [मध्य] लक्ष्य के समान है, तो -
-
सही लौटें
-
-
अगर अंक [मध्य] <लक्ष्य, तो −
-
कम :=मध्य + 1
-
-
अन्यथा
-
उच्च :=मध्य - 1
-
-
-
झूठी वापसी
-
मुख्य विधि से, निम्न कार्य करें -
-
रिट:=0
-
प्रत्येक तत्व के लिए मैं अंकों में
-
रिट:=रिट + सहायता (i, अंक)
-
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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;
}
};
main() {
Solution ob;
vector<int> v = {2,6,4,3,10};
cout << (ob.solve(v));
} इनपुट
{2,6,4,3,10} आउटपुट
3