1. Binary Search

while ( i + 1 < j) 模板

Rotated Array

Matrix里的二分查找

二分答案

Median of two sorted Array

• 经典难题

• 参考山景城1姐视频 3:10开始，10:50 https://www.youtube.com/watch?v=ScCg9v921ns

• cutA, cutB

• L1<=R2, L2<= R1

• 假设nums1.length <= nums2.length, 可以只对较短的nums做binary search, O(Log(min(m,n)))

• cutA是nums1的分界线，表示nums1分割线左边数组元素个数

• cutB是nums2的分界线，表示nums2分割线左边数组元素个数

• cutA和cutB左边的数肯定都是<=右边的数

• L1为cutA左边最大的数，R1为cutA右边最小的数

• L2为cutB左边最大的数，R2为cutB右边最小的数

• 规定左边的元素个数会等于或比右半边元素个数多1，这样当len为奇数时，median num = max(L1, L2）

• 问题转化成如何找到正确的cutA和cutB的位置--> L1<=R2, L2<= R1

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int lenA = nums1.length, lenB = nums2.length;
         //make sure nums1 is always shorter
        if (lenA > lenB) return findMedianSortedArrays(nums2, nums1);
        //lenA == 0
        if (lenA == 0) {
            return (double) (nums2[(lenB - 1) /2 ] + nums2[lenB / 2]) / 2.0; //trick to handle odd and even
        }
        int len = lenA + lenB;
        int startA = 0, endA = lenA;
        int cutA, cutB;
        while (startA <= endA) {
            cutA = startA + (endA - startA) / 2;
            cutB = (len + 1) / 2 - cutA;
            double L1 = cutA == 0 ? Integer.MIN_VALUE : nums1[cutA - 1];
            double L2 = cutB == 0 ? Integer.MIN_VALUE : nums2[cutB - 1];
            double R1 = cutA == lenA ? Integer.MAX_VALUE : nums1[cutA];
            double R2 = cutB == lenB ? Integer.MAX_VALUE : nums2[cutB];
            if (L1 > R2) {
                endA = cutA - 1;
            } else if (L2 > R1) {
                startA = cutA + 1;
            } else {
                if (len % 2 == 0) {
                    return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
                } else {
                    return Math.max(L1, L2);
                }
            }
        }
        return -1;
    }