C++ এ ইনসার্ট পজিশন অনুসন্ধান করুন

ধরুন আমাদের একটি সাজানো অ্যারে অ্যারে এবং একটি টার্গেট মান আছে, লক্ষ্যটি পাওয়া গেলে আমাদের সূচকটি খুঁজে বের করতে হবে। যদি এটি উপস্থিত না থাকে, তাহলে সূচীটি ফেরত দিন যেখানে এটি ক্রমানুসারে ঢোকানো হলে সেটি থাকবে৷

সুতরাং, যদি ইনপুট হয় [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[মধ্য]> লক্ষ্য, তারপর −

    • উচ্চ :=মধ্য - 1, অবস্থান :=মধ্য

  • অন্যথায়

    • নিম্ন :=মধ্য + 1, অবস্থান :=মধ্য + 1

• রিটার্ন pos

উদাহরণ

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

#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