二分搜索总结

前言

二分查找是一种常见的搜索方法，它利用数组的单调性将查找时间限制在了对数级范围，极大的提高了查询效率。二分搜索可以衍生出多种变种，且边界条件极容易弄错，因此需要对二分搜索进行一定的理解分析，才能在适合的场景选择适合的实现。

常见的用法

1. 查找是否包含某数

 public int binary(int[] nums, int l, int r, int num) {
        while(l <= r) {
            int mid = (l + r) / 2; 
            if(nums[mid] == num) {
                return mid;
            } else if(nums[mid] > num) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

几个可变的点，也是经常容易搞混弄错的地方：

• r = nums.length 或者 nums.length-1
• l < r 或者 l <= r
• r = mid 或者 r = mid-1
• return -1 或者 l 或者 r 或者 r-1

m = (l + r) / 2 此处须小心超出范围问题
r = nums.length 时，则l < r 且 r = mid
r = nums.length-1 时，则l <= r 且 r = mid-1

2. 查找插入点

当数组中有存在重复数字时，查找目标出现的最左位置或者找到插入位置。
例子：Search Insert Position
查找到可以插入的位置。

2.1 
public int lower_bound(int[] nums, int l, int r, int t) {
        while(l < r) {
            int m = (l + r) / 2;
            if(nums[m] >= t) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

2.2
public int lower_bound(int[] nums, int l, int r, int t) {
        while(l <= r) {
            int m = (l + r) / 2;
            if(nums[m] >= t) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

此情形仍须满足用法1中的条件。
同时 2.1 可以演化成用法1中查找具体值的问题，对返回的 l 进行判断：
(l == nums.length || nums[l] != t) 则表示没找到。

总结

解法2.1其实涵盖了用法1，因此2.1的用法可以解决很多二分查找问题及其衍生出的其它一些变种。