【二分查找】4. 寻找两个有序数组的中位数

 1 class Solution {
 2     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 3     int[] nums;
 4     int m = nums1.length;
 5     int n = nums2.length;
 6     nums = new int[m + n];
 7     if (m == 0) 
 8     {
 9         if (n % 2 == 0) 
10         {
11             return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
12         } 
13         else 
14         {
15 
16             return nums2[n / 2];
17         }
18     }
19     if (n == 0) 
20     {
21         if (m % 2 == 0) 
22         {
23             return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
24         } 
25         else 
26         {
27             return nums1[m / 2];
28         }
29     }
30 
31     int count = 0;
32     int i = 0, j = 0;
33     while (count != (m + n)) 
34     {
35         if (i == m) 
36         {
37             while (j != n) 
38             {
39                 nums[count++] = nums2[j++];
40             }
41             break;
42         }
43         if (j == n) 
44         {
45             while (i != m) 
46             {
47                 nums[count++] = nums1[i++];
48             }
49             break;
50         }
51 
52         if (nums1[i] < nums2[j]) 
53         {
54             nums[count++] = nums1[i++];
55         } 
56         else 
57         {
58             nums[count++] = nums2[j++];
59         }
60     }
61 
62     if (count % 2 == 0) 
63     {
64         return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
65     } 
66     else 
67     {
68         return nums[count / 2];
69     }
70 }
71 }

 1 class Solution {
 2 public:
 3     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
 4     {
 5         int n = nums1.size();
 6         int m = nums2.size();
 7 
 8         if (n > m)  
 9         {
10             // 保证数组1一定最短
11             return findMedianSortedArrays(nums2, nums1);
12         }
13 
14         // Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。
15         // LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。
16         int LMax1, LMax2, RMin1, RMin2;
17         int c1, c2, lo = 0, hi = 2 * n;  //我们目前是虚拟加了‘#‘所以数组1是2*n长度
18 
19         while (lo <= hi)   //二分
20         {
21             c1 = (lo + hi) / 2;  //c1是二分的结果
22             c2 = m + n - c1;
23 
24             LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
25             RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
26             LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
27             RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];
28 
29             if (LMax1 > RMin2)
30                 hi = c1 - 1;
31             else if (LMax2 > RMin1)
32                 lo = c1 + 1;
33             else
34                 break;
35         }
36         return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;        
37     }
38 };