二分法题型小结

在刷题的过程中，二分法用的还是挺多的，有时候超时了往往是你没有用上二分法，今天我就来稍微总结下用的最多的三种二分法搜索。

一、搜索和目标值相等的数

这一类是最简单的，例如对于数组 arr = {1, 2, 5, 6, 9}，要我们搜索返回目标数 target = 6，这个时候我们需要返回 6 的下标 i = 3。代码如下

int binarySearch(int[] arr, int target){
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

不过这个有一个需要注意的点，就是很多人在求 mid 的时候，会这样写

mid = (left + right) / 2;

其实这样写是有点小问题的，因为 left + right 有可能导致数值溢出，从而 mid 的计算就错误了，所以经常这样写的小伙伴要注意了，严谨的写法应该是这样写：

mid = left + (right - left) / 2;

二、 查找第一个不小于目标值的数

查找第一个不小于目标的数，我觉得这类出现的频率是最高的，而且要注意，目标数并不一定就出现在数组中。

例如对于数组 arr = {1, 2, 5, 6, 9}，目标数 target = 6，那么我们要返回下标 i = 4 。

又如 arr = {0, 1, 2, 2, 2, 3}，target = 2。我们要返回 i = 2。

代码如下

int binarySearch(int[] arr, int target){
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return right;
}

在代码上，和第一种最大的区别就是 right = mid - 1 变成 right = mid 了，至于为啥？自行脑补，随便找我上面举的例子模拟一下就行了。

对了，还有一种和查找第一个不小于目标值的数类似的题，就是找最后一个小于目标值的数。这很简单，直接返回 right - 1 就可以了。

文章首发于公众号『苦逼的码农』，更多经常文章欢迎搜索关注，已有150多篇原创。

三、查找第一个大于目标值的数

查找第一个大于目标的数，我觉得这类出现的频率也是最高的，而且也要注意，目标数并不一定就出现在数组中。

例如对于数组 arr = {1, 2, 5, 6, 9}，目标数 target = 6，那么我们要返回下标 i = 5 。

又如 arr = {0, 1, 2, 2, 2, 3}，target = 2。我们要返回 i = 5。

我们先来看下代码

int binarySearch(int[] arr, int target){
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return right;
}

有木觉得和第二种类型的代码太像了，只需要在 if 语句里吧 arr[mid] < target 改成 arr[mid] <= target 即可。至于为啥？因为第一个不小于和第一个大于等于是同一个意思，但是这道题是第一个大于，不包括等于这种情况啊。所以把 < 改为 <= 即可。

总结

其实对于二分法的查找，有很多种类型，不过，代码的差别都不大，就是有可能大于改成大于等于。left/right = mid + 1 变成 left/right = mid。所以有时也很容易出错，特别是脑子乱了的时候，所以我这里建议，选择一种自己喜欢的代码风格，然后每次做题的时候，的用你心中的那份模板代码。

当然，我上面说的这三种 还是比较简单的，还有一些比较难的，就是 target 可能是动态更新的，而且 left 和 right 的更新也比较复杂，不过对于这种，在 leetcode 一般都是 hard 级别的题了。所以大家可以先把上面这三种掌握起来，不过 你在做题时，并不会有直接说是哪种题型的话，甚至你都没有考虑到可以使用二分法来做，所以平时做题的时候可以多留意。