Chương trình tìm trung vị của hai mảng đã sắp xếp trong C++

Cho 2 mảng đã sắp xếp. Tìm trung vị của mảng hợp nhất. Ví dụ [1,5,8] và [2,3,6,9] → trung vị là 5.

Giải thuật (Tìm kiếm nhị phân trên phân hoạch)

• Đảm bảo mảng 1 ngắn hơn mảng 2.
• Tìm phân hoạch partitionX trên mảng 1, partitionY trên mảng 2 sao cho: số phần tử bên trái = số phần tử bên phải (hoặc chênh 1), và maxLeftX ≤ minRightY, maxLeftY ≤ minRightX.
• Dùng binary search điều chỉnh partitionX.
• Khi thỏa mãn: nếu tổng độ dài chẵn → trung vị = trung bình 2 giá trị giữa; lẻ → max của 2 bên trái.

Ví dụ triển khai

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

class Solution {
public:
    double solve(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) return solve(nums2, nums1);
        int x = nums1.size(), 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 (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0;
                } 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.solve(v1, v2);
    return 0;
}

Đầu vào

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

Đầu ra

5