Binary Search

Binary Search

对于sorted array，在不改变数据结构的前提下，Binary Search几乎总是最优的搜索方式。即将数据分成两部分，根据对当前节点的分析进行剪枝。在Binary Search时，总是应该检查逼近方式和逼近条件的关系：

• 求给定值的一个位置，可以用 $low <= high$ 作为搜索条件，根据 $A[mid]$ 与目标值的关系取 $low = mid + 1$ 或者 $high = mid - 1$ 逼近。

• 求下界的时候（给定值或范围），应该以 $low < high$ 作为搜索条件，应该在不符合条件时取 $low = mid + 1$，对应地， $mid = low + (high-low)/2$ 以保证每次循环都是逼近的。

• 求上界的时候（给定值或范围），应该以 $low < high$ 作为搜索条件，应该在不符合条件时取 $high = mid - 1$，对应地， $high = high - (high - low)/2$ 以保证每次循环都是逼近的。

大多数情况 Binary Search 是以 index 为搜索范围，但是也可以来搜索 value。例如，LC287。

经典题目

4 Median of Two Sorted Arrays

First, we use k/2 as our step length to pick two numbers from arrayA and arrayB starting from index 0. Then we keep the larger number, and move the left boundary of the array which has the smaller number. In this case, we could remove k/2 numbers, and we just need to find (k - k / 2)th smallest in the remaining numbers. Then, we use k/4 as our step, and do the same step as above, and then k/8, k/16... Until k == 1, then just return the smaller of the current two numbers.

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int aLength = nums1.length;
    int bLength = nums2.length;
    int length = aLength + bLength;
    
    if (length % 2 == 0) {
        int a = findKthSmallest(nums1, 0, nums2, 0, length / 2);
        int b = findKthSmallest(nums1, 0, nums2, 0, length / 2 + 1);
        return (a + b) / 2.0;
    } else {
        return 1.0 * findKthSmallest(nums1, 0, nums2, 0, length / 2 + 1);
    }
}

private int findKthSmallest(int[] a, int aLeft, int[] b, int bLeft, int k) {
    if (aLeft >= a.length) {
        return b[bLeft + k - 1];
    } else if (bLeft >= b.length) {
        return a[aLeft + k - 1];
    } else if (k == 1) {
        return Math.min(a[aLeft], b[bLeft]);
    }
    
    int aKthLeft = aLeft + k / 2 - 1 < a.length ? a[aLeft + k / 2 - 1] : Integer.MAX_VALUE;
    int bKthLeft = bLeft + k / 2 - 1 < b.length ? b[bLeft + k / 2 - 1] : Integer.MAX_VALUE;
    
    if (aKthLeft < bKthLeft) {
        return findKthSmallest(a, aLeft + k / 2, b, bLeft, k - k / 2);
    } else {
        return findKthSmallest(a, aLeft, b, bLeft + k / 2, k - k / 2);
    }
}

33 Search in Rotated Sorted Array

这道题考的是局部单调性如何求解。 根据单调区间的特性：nums[i] < nums[j] && i < j，则区间 [i, j] 单调递增

public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] > target) {
            if (nums[left] <= target || nums[mid] < nums[right]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (target <= nums[right] || nums[left] < nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

162 Find Peak Element

思路：因为两端是负无穷，所以必然存在至少一个peak element。二分查找，如果num[mid] > num[mid - 1]，说明右边必然存在一个解（左边可能存在），因为num[mid] > num[mid - 1] && num[mid] > 负无穷；同理，如果num[mid] > num[mid + 1]，说明左边必然存在一个解（右边可能存在）。

public int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if ((mid == 0 || nums[mid] > nums[mid - 1]) && (mid == nums.length - 1 || nums[mid] > nums[mid + 1])) {
            return mid;
        }
        if (mid == 0 || nums[mid] > nums[mid - 1]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

378 Kth Smallest Element in a Sorted Matrix

这道题是以 Value 为搜索范围。Lo = matrix[0][0], hi = matrix[n - 1][m - 1], mid = lo + (hi - lo) / 2。

每次循环，判断当前值(mid)所处的位置，可以count number of values <= mid，若count < k，则可以排除[lo, mid]这个区间，那么更新lo = mid + 1；若count == k，mid是潜在的答案，我们可以排除[mid + 1, hi]这个区间，所以hi = mid；若count > k，mid仍旧是潜在的答案，因为很多值可能有多个重复，所以hi = mid。

public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length, m = matrix[0].length;
    int lo = matrix[0][0], hi = matrix[n - 1][m - 1];
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int j = m - 1;
        int count = 0;
        for (int i = 0; i < n; i++) {
            while (j >= 0 && matrix[i][j] > mid) {
                j -= 1;
            }
            count += (j + 1);
        }
        if (count < k) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return hi;
}

528. Random Pick with Weight

class Solution {
	/*
		Method 1: Random & Binary Search.
		Time Complexity: O(log n)
		Get the total number, get a random number from [1, sum], find where it's located
	*/
	
    int[] array;
    Random rd = new Random();
    public Solution(int[] w) {
        array = new int[w.length];
        for (int i = 0; i < w.length; i++) {
            array[i] = (i == 0 ? w[i] : w[i] + array[i - 1]);
        }
    }
    
    public int pickIndex() {
        int num = rd.nextInt(array[array.length - 1]) + 1;
        int left = 0, right = array.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (array[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}