C++ এ কাকতালীয় অনুসন্ধান

ধরুন আমাদের কাছে সংখ্যা বলা অনন্য পূর্ণসংখ্যার একটি তালিকা আছে। আমাদের পূর্ণসংখ্যার সংখ্যা খুঁজে বের করতে হবে যা এখনও একটি আদর্শ বাইনারি অনুসন্ধান ব্যবহার করে সফলভাবে পাওয়া যেতে পারে।

সুতরাং, যদি ইনপুটটি [2,6,4,3,10] এর মত হয়, তাহলে আউটপুট হবে 3, যেমন আমরা 4 খুঁজতে বাইনারি অনুসন্ধান ব্যবহার করি, আমরা প্রথমে এটি খুঁজে পেতে পারি পুনরাবৃত্তি আমরা দুটি পুনরাবৃত্তির পরেও 2 এবং 10 খুঁজে পেতে পারি৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সাহায্য(), এটি লক্ষ্য, একটি অ্যারে এবং সংখ্যা,

  নেবে

• কম :=0

• উচ্চ :=সংখ্যার আকার - 1

• যখন কম <=উচ্চ, করুন −

  • মধ্য :=নিম্ন + (উচ্চ - নিম্ন) / 2

  • যদি nums[mid] টার্গেটের সমান হয়, তাহলে −

    • প্রত্যাবর্তন সত্য

  • যদি nums[mid]

    • নিম্ন :=মধ্য + 1

  • অন্যথায়

    • উচ্চ :=মধ্য - 1

• ফেরত মিথ্যা

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• ret :=0

• প্রতিটি উপাদানের জন্য i সংখ্যায়

  • ret :=ret + help(i, nums)

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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