Median of Two Sorted Arrays

题目
There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

答案

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        // Make sure len(A) <= len(B)
        if(A.length > B.length) {
            return findMedianSortedArrays(B, A);
        }
        int m = A.length, n = B.length;
        int left = 0, right = m, p = m + n;
        while(left <= right) {
            int partition_x = (left + right) / 2;
            int partition_y = (m + n + 1) / 2 - partition_x;
            
            int max_left_x = (partition_x == 0) ? Integer.MIN_VALUE : A[partition_x - 1];
            int min_right_x = (partition_x == m) ? Integer.MAX_VALUE : A[partition_x];
            
            int max_left_y = (partition_y == 0) ? Integer.MIN_VALUE : B[partition_y - 1];
            int min_right_y = (partition_y == n) ? Integer.MAX_VALUE : B[partition_y];
            
            if(max_left_x <= min_right_y && max_left_y <= min_right_x) {
                if(p % 2 == 0) return ((double)Math.max(max_left_x, max_left_y) + Math.min(min_right_x, min_right_y)) / 2;
                else return Math.max(max_left_x, max_left_y);
            }
            else if(max_left_x > min_right_y) {
                right = partition_x;
            }
            else {
                left = partition_x + 1;
            }
        }
        return 0;
    }
}