二分查找

  所谓二分查找，就是从一个查找范围中每次取中间值，然后根据中间值来判断是否满足条件或是缩小查找范围的过程，且这个范围内的值需要是有规律的，比如是有序的。

引子

  以 LeetCode 的一道简单题为例：给定一个排序数组和一个目标值，返回目标值的索引，若不存在，则返回能够插入该目标值的索引。

  如 ：array = [1,5,7,10,12], target = 6

  则返回值为 2

  这题就是经典的使用二分查找的场景，最开始的查找范围是 [0, 4]，中间值 array[2] = 7，根据这个中间值，我们知道 6 是小于中间值的，因此能够缩小查找范围，即 [0, 1]，继续判断中间值 array[0] = 1，缩小查找范围 [1, 1]，最后发现查找范围内只剩下一个值 5，且小于目标值 6 ，因此最后就能知道需要插入的索引是 2。

代码如下：

int upperBound(int r[],int left,int right,int x){
    int mid;
    while(left <= right){
        mid = (left + right) / 2;
        if(r[mid] == x){
            return mid;
        }else if(r[mid] > x){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

  其中， (left + right) / 2 有必要的话可以替换成 left + (right - left) / 2，以避免 left + right 超出整型范围的情况。

二分查找变形

  根据使用场景的不同，二分查找有一些变形算法。

  同样，以 剑指Offer （或 LeetCode）的一题为例，题目很简单，就是从一个有序数组中寻找数字 target 的出现次数，如 nums = [5,7,7,8,8,10] ，target = 8，程序输出 2，因为 8 出现了两次。

  因为数组有序，我们可以考虑使用二分查找把时间复杂度降为 log(n)。

  首先，使用二分查找找出第一个大于等于 target 的位置 lower ，本例中就是 3，再使用二分查找找到第一个小于等于 target 的位置 l，本例中就是 4，这样，数组中等于 target 的数字的出现次数就是 l - lower + 1，再考虑一些边界情况，即 target 未在数组中出现的情况，我们可以使用 nums[l] === target 来判断，若未出现过，返回 0 即可。

JS 代码如下：

var search = function(nums, target) {
    let l = 0, r = nums.length - 1;
	
    // 先找到第一个大于等于 target 的位置
    while (l < r) {
        let mid = l + Math.floor((r - l) / 2);
        if (nums[mid] < target) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    let lower = l;
    l = 0, r = nums.length - 1;
	
    // 再找到第一个小于等于 target 的位置
    while (l < r) {
        let mid = l + Math.ceil((r - l) / 2);
        if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid;
        }
    }
    
    if (nums[l] === target) {
        return l - lower + 1;
    } else {
        return 0;
    }
};

寻找第一个 《大于等于》 x 的位置

  在下面代码中，循环结束时，left 是会刚好等于 right 的，right 总是会在大于等于 x 的地方停下来，一直压缩区间，left 最后的位置会是第一个大于等于 x 的位置。

  如 [5,7,7,8,8,10] ，x = 8，那么当循环结束时， l = r = 3。

  如 arr = [1, 3, 4, 6, 7] ，x = 5，返回 3。

function upperBound(arr, tar) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let num = arr[mid];
        if (tar <= num) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

寻找第一个 《大于》 x 的位置

  这个函数与上面一个函数的变化只是将 if 判断中的 <= 改为 <。

  如 [5,7,7,8,8,10] ，x = 8，那么当循环结束时， l = r = 5。

function upperBound(arr, tar) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let num = arr[mid];
        if (tar < num) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

寻找第一个 《小于等于》 x 的位置

  同理，在循环中稍加变动，就能实现另一个效果，不过这时候计算 mid 需要向上取整了（之前都是向上取整的），不然可能会出现无限循环，因为每次都向下取整的话可能会出现 left 不变的情况（如索引相邻情况 ）：

  如 [5,7,7,8,8,10] ，x = 8，那么当循环结束时， l = r = 4。

  如 [1, 3, 4, 6, 7] ，x = 5，那么当循环结束时， l = r = 2。

function lowerBound(arr, tar) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        let mid = Math.ceil((left + right) / 2);
        let num = arr[mid];
        if (tar >= num) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
	return right;
}

寻找第一个 《小于》 x 的位置

  同理，第一个小于 x 的位置：

  如 [5,7,7,8,8,10] ，x = 8，那么当循环结束时， l = r = 2。

  如 [1, 3, 4, 6, 7] ，x = 5，那么当循环结束时， l = r = 2。

while (left < right) {
    let mid = Math.ceil((left + right) / 2);
    let num = arr[mid];
    if (tar > num) {
        left = mid;
    } else {
        right = mid - 1;
    }
}

 目录