[数据结构与算法]二分查找算法leetcode.4

 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) //交换使nums1长度较短
            return findMedianSortedArrays(nums2, nums1);
        int m = nums1.length;
        int n = nums2.length;
        //整体思路，分别将两个数组分割，使得数组左右数量的和近似相等，中间一个则并入左边(1)，并且左边最大值不大于右边最小值(2)，那么中位数在分割线附近
        //分割线两边的数要满足左上<=右下，左下<=右上,即(2),
        int left = 0, right = m;
        int max = 0, min = 0; //max前一部分的最大值,min后一部分的最小值
        //在nums1中二分查找唯一满足条件的分割线
        while (left <= right) {
            int i = (left + right) / 2;//nums1分割线，表示位于i位置前，表示分割线左边元素个数
            int j = (m + n + 1) / 2 - i;//nums2分割线，表示位于j位置前，表示分割线左边元素个数，

            // l1,r1,l2,r2 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]，考虑边界情况
            int l1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int r1 = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int l2 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int r2 = (j == n ? Integer.MAX_VALUE : nums2[j]);
            //判断是否满足(2)
            if(l1<=r2) {
                if(l2<=r1) {
                    max = Math.max(l1, l2);//求左边最大值
                    min = Math.min(r1, r2);//求右边最小值
                    break;
                }
                else left=i+1;
            } else {
                if (l2 <= r1)
                    right = i - 1;
            }
        }
        return (m + n) % 2 == 0 ? (max + min) / 2.0 : max;//判断总长度
    }