Binary Search (Java) - ShuweiLeung/Thinking GitHub Wiki

该页笔记始于"2018.7.26"，结于“2018.7.28”，使用Java语言

1.（852:Easy）Peak Index in a Mountain Array

从头到尾扫描一遍数组，找到第一个开始下降的索引返回即可。或者按照二分查找思路，寻找最大值。

2.（744:Easy）Find Smallest Letter Greater Than Target

该题利用二分查找，注意当指针指到letters数组最后一个位置时，要返回letters[0]。该题可以利用取余%操作，来解决target比letters数组最大的元素还要大于是返回letters[0]的情况。参考代码如下，注意学习下面代码中，low、high指针更新的分析思想，是mid+/-1还是直接取mid。

    public char nextGreatestLetter(char[] letters, char target) {
        int lo=0,hi=letters.length;
        while(lo<hi){
            int mi=(lo+hi)/2;
            if(target>=letters[mi])
                lo=mi+1;
            else //当target<letters[mi]时，letters[mi]可能就是答案，所以high更新为mid，而不是mid-1
                hi=mi;
        }
        return letters[lo%(letters.length)];  //利用取余操作保证当lo=letters.length时，返回letters[0]
    }

3.（374:Easy）Guess Number Higher or Lower

-1 : My number is lower

1 : My number is higher

0 : Congrats! You got it!

Here "My" means the number which is given for you to guess not the number you put into guess(int num).

4.（475:Easy）（经典题）Heaters

一个house可以选择两个炉子。左边的和右边的，哪个距离自己近，就选择被哪个炉子温暖，注意第一个heater左边的houses只能被第一个heater温暖，最后一个heater右边的houses只能被最后一个heater温暖，其余中间的房子，均可以被左边和右边的同时温暖，在所有的最近的半径里面选择最大的半径，就是题目要求求出的半径。
具体可以参看代码实现及注释

5.（278:Easy）First Bad Version

简单的二分查找的应用，具体实现请参看代码。

6.（704:Easy）Binary Search

最基本的二分查找的应用，具体实现请参看代码。

7.（436:Medium）（非常非常经典题）Find Right Interval

该题的返回结果集要与输入数组的interval对应，所以我们不能将输入数组按从大到小的顺序进行排列。因为我们只考虑"right"位置关系，所以只需要关注interval的起点及该interval在输入数组中的索引位置即可。
我们用List存储每个interval的起点及输入数组中索引位置i，并按照起点大小排序。当我们遍历输入数组来求答案时，借助之前建立的List集合用二分搜索查找比当前区间结尾处稍大于或等于的区间索引下标。
具体细节请参看代码实现。

8.（240:Medium）（非常非常经典题）Search a 2D Matrix II

该题最一般的方法是不管列升序的性质，对每一行都采取二分搜索，当所有行都搜索完后仍没有target后，返回false。
最经典的方法是，同时利用行升序和列升序的性质，将指针斜向移动。对于matrix[i][j]，当当前的值比target小时，我们只进行i++操作；当值比target大时，只进行j--操作。如果单单这两个条件显然这是不正确的，因为当matrix[i][j]<target时，可能target在(i,j)的下侧，也可能在(i,j)的右侧，但我们只在这里进行了下移的操作。实际上，如果在开始时我们将matrix[i][j]初始化为matrix[0][n-1]（matrix的top-right corner），那么上面的操作就是正确的，此时target若存在，相对于top-right corner而言，一定是在它的左下方的。参考代码如下：

    public boolean searchMatrix(int[][] matrix, int target) {
        // input validation
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

        // start from top right corner
        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                // go down
                i ++;
            } else {
                // go left
                j --;
            }
        }
        return false;
    }

9.（275:Medium）（经典题）H-Index II

该题有一种线性时间复杂度的解法，就是从后往前遍历，看看当前数字是否大于等于n-i，若大于等于则更新h为n-i否则返回之前的h值。
当然该题也可以用二分搜索的方法来求解，每次比较citations[mid]和h-mid的大小，若大于等于则将h更新，否则将low变为mid+1进行尝试。
具体的实现细节请参看代码。

10.（658:Medium）（非常经典题）Find K Closest Elements

这道题我的思路是根据二分查找找到离x最近的数的下标索引index，然后由index向两边延伸取一侧离x较近的数加入到结果集中。
更高级更高效的二分查找思路是：固定一个长度为k的滑动窗口，mid是滑窗的左边界，mid+k是滑窗的右边界，比较窗口左右边界与x的大小，最后退出二分查找while循环时，只需要从mid位置取连续k个数返回即可。
具体思路请参看代码实现。

Assume we are taking A[i] ~ A[i + k -1].

We can binary research i

We compare the distance between x - A[mid] and A[mid + k] - x

If x - A[mid] > A[mid + k] - x,

it means A[mid + 1] ~ A[mid + k] is better than A[mid] ~ A[mid + k - 1],

and we have mid smaller than the right i.

So assign left = mid + 1.

Reversely, it's similar.

11.（668:Hard）（非常非常经典题）Kth Smallest Number in Multiplication Table

我们可以清楚的看到第i行第j列的数等于i*j，根据这一点，可以很快的判断一个数x在n×m表中是第几大的：第i行小于等于x的数有min（n，x/i）个，将m行的值加起来即可(一行最多有n个数，所以要从n和x/i中取较小的值才有效)。根据这一特点我们可以判断一个数x是在第k大的数之前还是之后，从而就可以使用二分法来获取第k大的数。

12.（528:Hard）（非常非常经典题）Random Pick with Weight

Use accumulated freq array to get idx.

w[] = {2,5,3,4} => wsum[] = {2,7,10,14}

then get random val random.nextInt(14)+1, idx is in range [1,14]

idx in [1,2] return 0
idx in [3,7] return 1
idx in [8,10] return 2
idx in [11,14] return 3

then become LeetCode 35. Search Insert Position Time: O(n) to init, O(logn) for one pick Space: O(n)

13.（497:Medium）（经典题）Random Point in Non-overlapping Rectangles

用一个map保存面积和矩形信息，key是当前为止的矩形总共包括多少个整数坐标点，value是当前遍历的矩形的坐标。我们首先在area面积的基础上随机找到一个矩形，然后再以该矩形的长和宽为基准随机找该矩形的一个坐标。

14.（911:Medium）（非常经典题）Online Election

该题题意是：先输入两个同样长度的整数数组，分别代表时间(time)和人物(person), {time[i], person[i]}表示在time[i]投票给person[i] 然后对任意一个时间，返回当前时间谁的票数最多。
我们在初始化的时候用一个Map来存储在固定的投票时间t，获得最高票数的人lead。然后在query时间t的最高票数获得者时时，我们查找floor time，即比t小的最大时间t'时刻的最高票数者。

15.（1011:Medium）（非常非常经典题）Capacity To Ship Packages Within D Days

因为为了运输包裹，承重量至少是最大的weight值，否则最大weight的包裹永远不能运输；而承重量的最大值当然是所有包裹weight的和。因此我们用二分查找来解决该题。对于每一次的mid值，我们都遍历一次所有的包裹，查看需要几天才能运输完，若所需天数比目标值大，则增加load承重量，否则减少load。