1. //给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。 
    2. //
    3. // 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
    4. //
    5. // 
    6. //
    7. // 示例 1： 
    8. //
    9. // 输入：nums1 = [1,3], nums2 = [2]
    10. //输出：2.00000
    11. //解释：合并数组 = [1,2,3] ，中位数 2
    12. // 
    13. //
    14. // 示例 2： 
    15. //
    16. // 输入：nums1 = [1,2], nums2 = [3,4]
    17. //输出：2.50000
    18. //解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
    19. // 
    20. //
    21. // 示例 3： 
    22. //
    23. // 输入：nums1 = [0,0], nums2 = [0,0]
    24. //输出：0.00000
    25. // 
    26. //
    27. // 示例 4： 
    28. //
    29. // 输入：nums1 = [], nums2 = [1]
    30. //输出：1.00000
    31. // 
    32. //
    33. // 示例 5： 
    34. //
    35. // 输入：nums1 = [2], nums2 = []
    36. //输出：2.00000
    37. // 
    38. //
    39. // 
    40. //
    41. // 提示： 
    42. //
    43. // 
    44. // nums1.length == m 
    45. // nums2.length == n 
    46. // 0 <= m <= 1000 
    47. // 0 <= n <= 1000 
    48. // 1 <= m + n <= 2000 
    49. // -106 <= nums1[i], nums2[i] <= 106 
    50. // 
    51. // Related Topics 数组 二分查找 分治算法 
    52. // 👍 3718 👎 0

    查找中位数，而且特意提醒了O(log (m+n))复杂度。
    有到log到情况一般都是要二分的，因此这题是对两个数组进行二分。
    这题写起来还是挺烦的，我本来就对边界值不敏感，对着别人对题解都把边界值写错。

    大体思路就是，因为整体数组长度是知道的，就是m+n。
    因此对nums1进行二分对时候也变相在对nums2进行二分，假设nums1划分到a位置，nums2也就相应到划分到(m+n)/2 - a。
    因此保证划分的分割线左边的数小于右边即可。

    2. class Solution {
    3.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    4.         int m = nums1.length;
    5.         int n = nums2.length;
    6.         if (m > n) {
    7.             return findMedianSortedArrays(nums2, nums1);
    8.         }
    10.         int left = 0;
    11.         int right = m;
    12.         // 分割线左边的总数字，+1是为了保证如果奇数的话，left划到左边多一个
    13.         int totalLeft = (m + n + 1) / 2;
    14.         while (left < right) {
    15.             // 划好分割线
    16.             int i = (left + right + 1) / 2;
    17.             int j = totalLeft - i;
    18.             // 保证分割线左边的要小于右边
    19.             if (nums1[i - 1] > nums2[j]) {
    20.                 // 分割线左边大于右边说明划的偏右了，要向左
    21.                 right = i - 1;
    22.             }else {
    23.                 left = i;
    24.             }
    25.         }
    27.         int i = left;
    28.         int j = totalLeft - i;
    30.         int n1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
    31.         int n1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
    32.         int n2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
    33.         int n2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
    35.         // 因为保证了如果奇数的话，left划到左边多一个，所以如果奇数直接返回左边最大的
    36.         if ((m + n) % 2 == 1) {
    37.             return Math.max(n1LeftMax, n2LeftMax);
    38.         }
    39.         // 否则返回中位数左右的中位数
    40.         return (double) (Math.max(n1LeftMax, n2LeftMax) + Math.min(n1RightMin, n2RightMin)) / 2;
    41.     }
    42. }