你还不懂二分查找?那是你没看这篇文章

⭐ 前言

关于 二分查找,我之前写过一篇简单的文章,但是因为太过于简单,加上各方面考虑不周,所以自己利用空余时间,重新看了书籍,阅读了大量博客,重新写了一篇 进阶版????

二分法的思想十分容易理解,但还是很多人对二分感到很苦恼,很困惑,可能是因为 二分的边界 很难掌握,也许是判断条件难写…

二分法细节确实比较多,但是真正理解之后,是可以有一个通用模板的,根本不需要考虑到底是开区间还是闭区间,加一还是减一还是不加减,更不需要打补丁。

然而,很幸运,你找到了这篇文章,仔细看下去,这篇文章将带你 学透二分 !!!

Let’s get it!

目录

二分查找

????小故事:

小明和冰冰在玩猜数字的游戏;

 

游戏规则:在1~100中,冰冰随便想一个数字,让小明来猜,游戏开始啦!

你还不懂二分查找?那是你没看这篇文章

假设小明从1开始依次往上猜,猜测过程会是这样:

你还不懂二分查找?那是你没看这篇文章

(这是简单查找,更准确的说法是傻找。每次猜测都只能排除一个数字。如果冰冰想的数字是 99,小明得猜 99次 才能猜到!)

于是另一种更佳的猜法。小明直接从 50 开始猜。

你还不懂二分查找?那是你没看这篇文章

小了,但排除了一半的数字!至此,小明知道1~50都小了。接下来,小明猜 75

你还不懂二分查找?那是你没看这篇文章

大了,那余下的数字又排除了一半!使用二分查找时,小明猜测的是中间的数字,从而每次都将余下的数字排除一半。接下来,小明猜 63(50和75中间的数字)。

你还不懂二分查找?那是你没看这篇文章

这就是二分查找,小明学习了第一种算法!每次猜测排除的数字个数如下

你还不懂二分查找?那是你没看这篇文章

不管冰冰心里想的是哪个数字,小明在 7 次之内都能猜到,因为每次猜测都将排除很多数字!

????思考:

假设你要在字典中查找一个单词,而该字典包含 240000 个单词,你认为每种查找最多需要多少步?

 

如果要查找的单词位于字典末尾,使用简单查找将需要 240000 步。

使用二分查找时,每次排除一半单词,直到最后只剩下一个单词。

你还不懂二分查找?那是你没看这篇文章

因此,使用二分查找只需 18 步——少多了!一般而言,对于包含n个元素的列表,用二分查找最多需要 log₂n 步,而简单查找最多需要 n 步。

(以上示例出自《算法图解》)

✨ 总结二分

我自己总结了会运用到 二分查找 的几种情况,

我们先假设数组是升序排列,再给你一个数target

如下图:

你还不懂二分查找?那是你没看这篇文章

????‍????思路:进阶版一和进阶版二应该尽量用同一种方法解决,而不需要考虑太多不一样的细节。而在我的思路中,进阶版一二三四都是同一个套路,Don’t Blink

???? 基础版

首先你需要知道最基础版应该怎么写,二分法的思想其实很简单,就是先取中间的数,然后和target比较,如果小了就往右找,大了就往左找。然后再取中间数,如此循环,直到中间没有数了。

思路我相信大家都能理解,但是在写法上,实际上还有一个 双指针 的思想,也就是我们需要left和right两个指针,然后不断调整两个指针的位置,最终得到答案。

下面我们通过一个例子来帮助我们理解。

我们需要在 nums 数组中,查询元素 8 的索引

你还不懂二分查找?那是你没看这篇文章

(1)我们需要定义两个指针分别指向数组的头部尾部,这是我们在整个数组中查询的情况,当我们在数组某一区间进行查询时,可以输入数组,起始位置,终止位置进行查询。

你还不懂二分查找?那是你没看这篇文章

(2)找出mid,该索引为mid =(left + right)/ 2,但是这样写有可能溢出,所以我们需要改进一下写成mid = left +(right - left)/ 2 或者 left + ((right - left ) >> 1) 两者作用是一样的,都是为了找到两指针的中间索引,使用位运算的速度更快。那么此时的 mid = 0 + (8-0) / 2 = 4

你还不懂二分查找?那是你没看这篇文章

(3)此时我们的 mid = 4nums[mid] = 6 < target,那么我们需要移动我们的 left 指针,让left = mid + 1,下次则可以在新的 left 和 right 区间内搜索目标值,下图为移动前和移动后:

你还不懂二分查找?那是你没看这篇文章

(4)我们需要在 left 和 right 之间计算 mid 值,mid = 5 + (8 - 5)/ 2 = 6 然后将 nums[mid]与 target 继续比较,进而决定下次移动left 指针还是 right 指针,见下图:

你还不懂二分查找?那是你没看这篇文章

(5)我们发现 nums[mid] > target,则需要移动我们的 right 指针, 则 right = mid - 1;则移动过后我们的 left 和 right 会重合,这里是我们的一个重点大家需要注意一下,后面会对此做详细叙述。

你还不懂二分查找?那是你没看这篇文章

(6)我们需要在 left 和 right 之间继续计算 mid 值,则 mid = 5 +(5 - 5)/ 2 = 5 ,见下图,此时我们将 nums[mid] 和 target 比较,则发现两值相等,返回 mid 即可 ,如果不相等则跳出循环,返回 -1

你还不懂二分查找?那是你没看这篇文章

二分查找的执行过程如下:


1.从已经排好序的数组或区间中,取出中间位置的元素,将其与我们的目标值进行比较,判断是否相等,如果相等则返回。

2.如果 nums[mid] 和 target 不相等,则对 nums[mid] 和 target 值进行比较大小,通过比较结果决定是从 mid的左半部分还是右半部分继续搜索。

如果 target > nums[mid] 则右半区间继续进行搜索,即left = mid + 1; 若target < nums[mid]则在左半区间继续进行搜索,即 right = mid -1;

????‍????动图解析:

你还不懂二分查找?那是你没看这篇文章

????代码示例

废话不多说,我们看一下代码

int binarySearch(int *nums, int sz, int target)
{
    int left = 0;//左下标
    int right = sz - 1;//右下标

    while (left <= right) 
    {
        //计算mid
        int mid = left + ((right - left) >> 1);

        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            //移动左下标
            left = mid + 1;
        }
        else {
            //移动右下标
            right = mid - 1;
        }
    }
    //没有找到该元素,返回-1
    return -1;
}

int main()
{
    int target = 8;//我们要查找的数字

    int nums[] = { 1,3,4,5,6,8,12,14,16 };

    int sz = sizeof(nums) / sizeof(nums[0]);

    int ret = binarySearch(nums, sz, target);

    if (-1 == ret) {
        printf("nums数组中不存在traget\n");
    } else {
        printf("找到了,下标是%d,数字是%d\n", ret, target);
    }
    return 0;
    
}

运行结果:

你还不懂二分查找?那是你没看这篇文章

????‍????解析:


我相信大家可能看过其他版本,比如所谓的开区间版本,但是我告诉大家,没有必要去看去记这么多版本,你只要会一种就能解万题!!!,而我建议大家就写上面这种。

这种也叫闭区间版本,每一个数都会搜索到,需要注意的几个点

1、right初始是sz-1,很好理解,因为这是数组右边界下标

2、while里面是left <= right,也好理解,因为我们每个数都要搜索,当left = right时,我们当然要进里面再判断一下

3、区间范围缩小时,left=mid+1或者right=mid-1,也好理解,因为nums[mid]已经不是我们要找的数,所以范围需要加一或者减一

二分查找的思路及代码已经理解了,那么我们来看一下实现时容易出错的地方

1、计算 mid 时 ,不能使用 (left + right )/ 2,否则有可能会导致溢出

2、while (left < = right) 注意括号内为left <= right ,而不是 left < right ;

我们继续回顾刚才的例子,如果我们设置条件为 left < right 则当我们执行到最后一步时,则我们的 left 和 right 重叠时,则会跳出循环,返回 -1,区间内不存在该元素,但其实不是这样的!

我们的 left 和 right 此时指向的就是我们的目标元素 ,但是此时 left = right 跳出循环(因为我们的while循环条件是:left < right)

3、left = mid + 1, right = mid - 1 而不是 left = mid 和 right = mid。

我们思考一下这种情况,见下图:当我们的 target 元素为 16 时,然后我们此时 left = 7 ,right = 8,mid = left + (right - left) = 7 + (8-7) = 7,那如果设置 left = mid 的话,则会进入死循环,mid 值一直为7 。

你还不懂二分查找?那是你没看这篇文章

之所以要推荐闭区间版本,是因为它最符合我们的直观逻辑,而且它是对称的,是把left和right一视同仁,而不会像有的版本left需要加一,但是right却不需要减一。

???? 进阶版一

有了基础版,那么如何在基础版的代码上进行升级呢?

先来看问题:

找到等于target的左边界(数组中可能有多个数都等于target),找不到返回-1

说实话,如果是第一次碰到这个问题,还真不一定能找到最优解!

第一个直观感受可能是我找到mid后,在往左一个一个地看,看看哪里是边界,但是这样,时间复杂度可能退化成o(n)!

其实还是应该用二分的思想找,关键在于nums[mid] == target时候的处理。

????代码示例

int binarySearch(int* nums, int sz, int target)
{
    int left = 0;//左下标
    int right = sz - 1;//右下标
    
    int flag = -1;
    while (left <= right)
    {
        //计算mid
        int mid = left + ((right - left) >> 1);

        if (nums[mid] == target) {
            flag = mid;
            right = mid - 1;
        }
        else if (nums[mid] < target) {
            //移动左下标
            left = mid + 1;
        }
        else {
            //移动右下标
            right = mid - 1;
        }
    }
    //没有找到该元素,返回-1
    return flag;
}

????解析:


这里的一个技巧就是当arr[mid] == target时,因为要找左边界,我们把right=mid-1,也就是改变右边界从而缩小范围。

这时候其实存在两种情况,要么答案已经是flag(左边界),[left,right]里面已经没有答案,while再也不会更新flag,最终返回flag是正确的,

要么flag还不是最终答案,那么答案就会在[left,right]里面,而在while中,我们总能找到它从而更新flag,最终返回flag也是正确的。

这里我们额外定义了一个flag表示结果,这一步是整个解法的精髓。相对于很多其他教程在考虑到底是返回left还是left+1还是right还是right-1,直接定义一个flag要好理解得多。

????‍这里也要注意几点:

1、flag一定是符合条件的,比如在这里,我们只有当arr[mid] == target的时候,我们才会更新flag。

2、flag会随着搜索范围减小越来越接近答案,当搜索结束时,flag就是答案。

3、如果一次都没有更新flag,说明整个数组里没有满足条件的数,flag应该为-1,也就是初始值。

???? 进阶版二

先看问题:

找到等于target的右边界(数组中可能有多个数都等于target),找不到返回-1

理解了上面的进阶版一,我相信这个问题都不需要我解释,直接看代码就行,

????代码示例

int binarySearch(int* nums, int sz, int target)
{
    int left = 0;//左下标
    int right = sz - 1;//右下标
    int flag = -1;
    while (left <= right)
    {
        //计算mid
        int mid = left + ((right - left) >> 1);

        if (nums[mid] == target) {
            flag = mid;
            left = mid + 1;
        }
        else if (nums[mid] < target) {
            //移动左下标
            left = mid + 1;
        }
        else {
            //移动右下标
            right = mid - 1;
        }
    }
    //没有找到该元素,返回-1
    return flag;
}

同样,在进阶版三和进阶版四中,只需要考虑什么时候更新flag;

???? 进阶版三

先看问题:

找到小于target的最大值,找不到返回-1

因为要找的数是小于target的,所以应该在arr[mid] < target时更新flag

????代码示例

int binarySearch(int* nums, int sz, int target)
{
    int left = 0;
    int right = sz - 1;
    int flag = -1;
    while (left <= right)
    {

        int mid = left + ((right - left) >> 1);
        if (nums[mid] < target) {
            flag = mid;
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return flag;
}

???? 进阶版四

先看问题:

找到大于target的最小值,找不到返回-1

因为要找的数是大于target的,所以应该在arr[mid] > target时更新flag

????代码示例

int binarySearch(int* nums, int sz, int target)
{
    int left = 0;
    int right = sz - 1;
    int flag = -1;
    while (left <= right)
    {

        int mid = left + ((right - left) >> 1);
        if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            flag = mid;
            right = mid - 1;
        }
    }
    return flag;
}

???? 结语

其实我看了网上很多讲二分查找的文章,包括公众号和知乎的,我认为,讲得都比较不是很通俗易懂;

像有些文章还介绍了:第一种写法、第二种写法、什么左闭右闭、左闭右开…

我看了都觉得头晕????

给大家推荐Linux之父Linus采访的一个视频:采访Linux之父Linus Torvalds:Linux背后的思想

大致意思就是说:所有的教科书都会告诉我们要分情况,但是我们要从另外一个角度看,如果两种情况可以统一,而一个逻辑统一的代码才是好代码!

????你知道的越多,你不知道越多,我们下期见!


上一篇:【C语言】一道有趣的喝汽水问题(会不会喝?喝不喝?)


下一篇:「数据结构」室友打一把王者就学会了冒泡排序算法