在两个有序数组间实现二分查找。

题目链接-来源：力扣（LeetCode）

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

思路：

二分法的实现需要考虑的越界条件比较多，我们考虑依次遍历。
数组总长度为 len = m + n，当总长为奇数时，中位数为中间值，否则为中间两数的平均值。为了统一中位数的表达，我们依然用两个目标指针 len / 2 和 (len + 1) / 2 + 1 记录中点值并取平均得到中位数，当总长为奇数时，这两个数相等，否则，这两个数为中点两侧的值。
用一个计数值 i 不停计数我们遍历过的数字，用另外两个指针 i1 和 i2 分别记录两个数组中下次当前遍历位置。哪一个值更小，我们就优先排除哪个，当遍历到到 i = len / 2 和 i = (len + 1) / 2 + 1 后，记录这两个值，求平均即可。
时间复杂度：O(m + n)
空间复杂度：O(1)

实现：

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        int i1 = 0;
        int i2 = 0;
        int i = 0;
        int medi2 = len / 2;
        int medi1 = (len + 1) / 2 - 1;
        double med2 = 0;
        double med1 = 0;
        // 两数组未穷尽
        while (i1 < len1 && i2 < len2) {
            // 是否为中位数
            if (i == medi1) {
                med1 = Integer.min(nums1[i1], nums2[i2]);
            }
            if (i == medi2) {
                med2 = Integer.min(nums1[i1], nums2[i2]);
                break;
            }
            
            // 步进
            if (nums1[i1] < nums2[i2]) {
                i1++;
            } else {
                i2++;
            }
            i++;            
        }
        
        // nums2穷尽，只考虑nums1
        while (i1 < len1 && i2 >= len2) {
            // 是否为中位数
            if (i == medi1) {
                med1 = nums1[i1];
            }
            if (i == medi2) {
                med2 = nums1[i1];
                break;
            }
            
            // 跳到中位数下标
            if (i < medi1) {
                i1 += medi1 - i;
                i = medi1;
            } else {
                i1 += medi2 - i;
                i = medi2;
            }
        }
        
        // nums1穷尽，只考虑nums2
        while (i2 < len2 && i1 >= len1) {
            // 是否为中位数
            if (i == medi1) {
                med1 = nums2[i2];
            }
            if (i == medi2) {
                med2 = nums2[i2];
                break;
            }
            
            // 跳到中位数下标
            if (i < medi1) {
                i2 += medi1 - i;
                i = medi1;
            } else {
                i2 += medi2 - i;
                i = medi2;
            }
        }
        return (med1 + med2) / 2;
    }
}