একটি সোর্টেড অ্যারে এবং টার্গেট ভ্যালু দেওয়া আছে। টার্গেট পাওয়া গেলে তার ইন্ডেক্স, না পাওয়া গেলে সেটি কোথায় ইনসার্ট করা উচিত তার ইন্ডেক্স রিটার্ন করুন।
উদাহরণ: [1,3,4,6,6], target=5 -> 3 (ইন্ডেক্স ৩-এ ৫ ইনসার্ট করলে [1,3,4,5,6,6])।
সমাধানের ধাপসমূহ
- বাইনারি সার্চ ব্যবহার করুন।
- 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, high = n-1, mid, 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
