C++-এ দুটি সোর্টেড অ্যারেতে মেডিয়ান (Median of Two Sorted Arrays)

ধরুন আমাদের কাছে দুটি সোর্টেড অ্যারে আছে। আমাদের কাজ হল এই দুটি অ্যারের মেডিয়ান (median) খুঁজে বের করা। যেমন, অ্যারেগুলো [1,5,8] এবং [2,3,6,9] হলে উত্তর হবে ৫।

সমাধানের ধাপসমূহ (বাইনারি সার্চ পদ্ধতি):

findMedianSortedArrays ফাংশন সংজ্ঞায়িত করুন যা nums1 এবং nums2 গ্রহণ করবে
যদি nums1.size() > nums2.size() হয়, তবে findMedianSortedArrays(nums2, nums1) কল করুন
x := nums1.size(), y := nums2.size()
low := 0, high := x
totalLength := x + y
যখন low <= high: partitionX = low + (high-low)/2, partitionY = (totalLength+1)/2 - partitionX
maxLeftX, minRightX, maxLeftY, minRightY হিসাব করুন (partition বাউন্ডারি অনুযায়ী)
যদি maxLeftX <= minRightY এবং maxLeftY <= minRightX হয়: যদি totalLength জোড় হয় তবে (max(maxLeftX,maxLeftY) + min(minRightX,minRightY))/2 রিটার্ন করুন, অন্যথায় max(maxLeftX, maxLeftY) রিটার্ন করুন
অন্যথায় maxLeftX > minRightY হলে high = partitionX-1, অন্যথায় low = partitionX+1
০ রিটার্ন করুন (যদি কোনো সমাধান না পাওয়া যায়)

উদাহরণ (C++)

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

class Solution { 
public: 
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) { 
        if(nums1.size() > nums2.size()) 
            return findMedianSortedArrays(nums2, nums1); 
        int x = nums1.size(); 
        int y = nums2.size(); 
        int low = 0, high = x; 
        int totalLength = x + y; 
        while(low <= high) { 
            int partitionX = low + (high - low) / 2; 
            int partitionY = (totalLength + 1) / 2 - partitionX; 
            int maxLeftX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1]; 
            int minRightX = (partitionX == x) ? INT_MAX : nums1[partitionX]; 
            int maxLeftY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1]; 
            int minRightY = (partitionY == y) ? INT_MAX : nums2[partitionY]; 
            if(maxLeftX <= minRightY && maxLeftY <= minRightX) { 
                if(totalLength % 2 == 0) 
                    return ((double)max(maxLeftX, maxLeftY) + (double)min(minRightX, minRightY)) / 2; 
                else 
                    return max(maxLeftX, maxLeftY); 
            } 
            else if(maxLeftX > minRightY) high = partitionX - 1; 
            else low = partitionX + 1; 
        } 
        return 0; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v1 = {1,5,8}, v2 = {2,3,6,9}; 
    cout << (ob.findMedianSortedArrays(v1, v2)); 
    return 0;
}

ইনপুট

[1,5,8] [2,3,6,9]

C++-এ দুটি সোর্টেড অ্যারেতে মেডিয়ান (Median of Two Sorted Arrays)

উদাহরণ (C++)

ইনপুট

আউটপুট