4. Median of Two Sorted Arrays 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        // 当元素总个数为奇数时，中位数放至分隔线右侧
        int expectedNums1LeftSize = (nums1.length + nums2.length) / 2;
        int left = 0, right = nums1.length; // 搜索 nums1 的 size, [left, right]

        while (left <= right) {
            // nums1 = [1, 2 |]
            // nums2 = [| 3, 4, 5]
            int nums1SubSize = (left + right) >>> 1, nums2SubSize = expectedNums1LeftSize - nums1SubSize;

            int nums1LeftBoundary = nums1SubSize == 0 ? Integer.MIN_VALUE : nums1[nums1SubSize - 1];
            int nums1RightBoundary = nums1SubSize == nums1.length ? Integer.MAX_VALUE : nums1[nums1SubSize];
            int nums2LeftBoundary = nums2SubSize == 0 ? Integer.MIN_VALUE : nums2[nums2SubSize - 1];
            int nums2RightBoundary = nums2SubSize == nums2.length ? Integer.MAX_VALUE : nums2[nums2SubSize];

            if (nums1LeftBoundary > nums2RightBoundary) {
                // nums1 = [4, | 5, 6]
                // nums2 = [1, 2, | 3]
                right = nums1SubSize - 1;
            } else if (nums2LeftBoundary > nums1RightBoundary) {
                // nums1 = [| 1, 2, 3]
                // nums2 = [3, 4, 5 |]
                left = nums1SubSize + 1;
            } else {
                int totalSize = nums1.length + nums2.length;

                boolean odd = ((totalSize) & 1) == 1;
                int leftMax = Math.max(nums1LeftBoundary, nums2LeftBoundary);
                int rightMin = Math.min(nums1RightBoundary, nums2RightBoundary);
                if (odd) {
                    return rightMin;
                } else {
                    return (leftMax + rightMin) / 2.0;
                }
            }
        }

        return 0; // cannot be
    }
}

References

4. Median of Two Sorted Arrays