测试开发基础之算法(8):二分查找的6种常用应用场景_二分查找的应用场景-程序员宅基地

技术标签: 数据结构与算法  

二分查找是针对有序数据集合的查找算法,一种非常简单易懂的快速查找算法,查找效率非常高,时间复杂度达到O(logn)。日常生活中经常会用到二分查找算法,比如猜数字游戏,查找字典的某一页等。

拿查找字典中某一页为例,假设一个字典一共500页,你想查找第200页的内容,那么你先随机翻开字典,如果翻开的页码比200小,则在字典的后半部分继续查找,如果翻开的页面比200大,则在字典的前半部分继续查找。之后,继续讲翻到的页码与期望的页码作对比,直到相等,结束查询。

本文就详细了解一下二分查找的具体算法及实现,虽然在工作中我们不可能手写一个二分查找算法。但是了解二分查找的原理和使用,对我们提高编码能力还是很有帮助的。

1. 二分查找的时间复杂度

二分查找是一种非常高效的查找算法,因为每次查找,都将数据减少到原来的一半,直到查找区间被缩小为空,才停止。整个查找过程被查数据的规模是一个等比数列:
在这里插入图片描述
第k次查找时,数据规模是n/2k,当k=log2n时,数据规模是1,次数就找到了待查元素。因此时间复杂度是O(logn)。
logn 是一个非常“恐怖”的数量级,即便 n 非常非常大,对应的 logn 也很小。比如 n 等于 2 的 32 次方,这个数很大了吧?大约是 42 亿。也就是说,如果我们在 42 亿个数据中用二分查找一个数据,最多需要比较 32 次。

2. 最简单的二分查找的实现

当查询集合不包含重复数据时,用二分查找在其中查询值等于给定值的数据。这是二分查找最简单的场景。
我们可以利用上一节笔记中掌握的递归算法来实现这个二分查找算法,代码如下:

def bsearch(nums: list, low: int, high: int, value) -> int:
    """
    在数组nums的下标low和high之间,查找value,返回下标
    """
    if low > high:
        return -1
    middle = low + (high - low) >> 1
    if nums[middle] == value:  # 找到了
        return middle
    elif nums[middle] > value:
        return bsearch(nums, low, middle-1, value)  # high = middle-1
    else:
        return bsearch(nums, middle+1, high, value)  # low = middle+1


print(bsearch([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 0, 9, 5))

用递归来表达二分查找,逻辑很清晰,重点是要注意一下几点:

  • 递归终止条件
    low > high
  • middle的取值
    middle=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话,两者之和就有可能会溢出。最好写成middle=low+(high-low)/2,或者middle=low+(high-low)>>1。
  • low和high的更新
    high = middle-1,和low = middle+1。千万别写成high=middle,low=middle,这样容易造成死循环
    除了用递归算法实现二分查找,循环迭代算法其实也很容易理解。代码如下:
def bsearch(nums: List[int], target: int) -> int:
    left= 0
    right=len(nums) - 1
    while left <= right: # 区间没有变成1个元素,就查找
        middle =  left + ((right-left) >> 1)  # 计算中间下标
        if nums[middle] == target:  # 找到了
            return middle
        elif nums[middle] < target:  # 中间下标比查找的值小,继续在右边查找
            left = middle + 1
        else:  # 中间下标比查找的值大,继续在左边查找
            right = middle - 1
    return -1

print(bsearch([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 0, 9, 5))

3. 二分查找应用场景的局限性

虽然二分查找的效率很高,但是它的应用场景也具有很大的局限性。

  • 首先,只能查找顺序存储的数据集

顺序存储的数据结果就是数组了,也就是二分查找只能从数组中查找,而不能查找链式存储的数据集,比如查找链表中的数,就不能用二分查找。

  • 其次,针对的是静态有序数据集

从有序集合中查找,我们很容易理解,但是静态有序是啥意思呢? 这个意思是说,二分查找适合那种不经常变动的数据集合。如果经常插入、删除的数据集,每次插入和删除都要保证集合数据的有序,维护动态数据有序的成本是很高的。

所以二分查找适合从有序的不经常变动的数据集合中查找。适合数据集合已经排好序,但是需要经常查找的场景。

  • 二分查找不适合数据量太大或者太小的场景
    因为二分查找需要依赖数组这种数据结构,而数组要求连续的内存空间,因此数据量太大的,会消耗太多的连续内存,对内存要求比较高。

那数据量太小,会有什么问题呢?如果数据量只有几十个,那么不论是使用二分查找还是顺序遍历,查找效率都差不多。

4. 查找第一个值等于给定值的元素

前面第二节,是在不存在重复元素的有序数组中,查找值等于给定值的元素的场景。那么如果有重复元素,二分查找的算法又该怎么写呢?

比如下面这样一个有序数组[1,2,3,5,5,5,5,6,7],其中,下标3,4,5,6的值都等于 5,是重复的数据。第一个等于5的数据下标是 3。如果用上面的二分查找代码,找到的值为5的下标是4,这样就不符合我们第一个值为5的下标的要求了。

我们知道中间下标的值nums[middle],跟要查找的 value 的大小关系有三种情况:大于、小于、等于。对于nums[middle]>value 的情况,我们需要更新 high= middle-1;对于nums[middle]<value 的情况,我们需要更新 low=mid+1。这两点都很好理解。
当nums[middle]==value时,对于没有重复数据的数组,直接返回middle即可。对于有重复数据的数组,要想返回middle,需要满足两个条件:如果middle 等于 0,则返回middle。或者middle不等于0,还要判断一下它的前一个,即middle-1的位置的值不等于value,才能返回middle。

我们对第二节的代码中,nums[middle]==value的那段代码进行一下修改:

def bsearch_2(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    while left <= right:  # 区间没有变成1个元素,就查找
        middle = left + ((right - left) >> 1)  # 计算中间下标
        if nums[middle] == target:
            if middle == 0 or nums[middle - 1] != target: # 关键点
                return middle
            else: # 前半部分肯定还有值为target的数据,继续在前半部分查找
                right = middle - 1
        elif nums[middle] < target:  # 中间下标比查找的值小,继续在右边查找
            left = middle + 1
        else:  # 中间下标比查找的值大,继续在左边查找
            right = middle - 1
    return -1

nums[middle] 前面的一个元素nums[middle-1] 也等于 value,那说明此时的 nums[middle] 肯定不是我们要查找的第一个值等于给定值的元素,这时要更新 high=middle-1,因为要找的元素肯定出现在 [left, middle-1] 之间。

5.查找最后一个值等于给定值的元素

跟前面的逻辑类似,代码如下:

def bsearch_3(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    while left <= right:  # 区间没有变成1个元素,就查找
        middle = left + ((right - left) >> 1)  # 计算中间下标
        if nums[middle] == target:
            if middle == right or nums[middle + 1] != target: # 关键点
                return middle
            else: # 后部分肯定还有值为target的数据,继续在后半部分查找
                left = middle + 1
        elif nums[middle] < target:  # 中间下标比查找的值小,继续在右边查找
            left = middle + 1
        else:  # 中间下标比查找的值大,继续在左边查找
            right = middle - 1
    return -1

6.查找第一个大于等于给定值的元素

比如有一个数组是[3,4,6,7,10],找到第一个大于等于5的元素下标。这个问题的解决思路和前面问题的实现思路一致。
继续改造前面的代码:

def bsearch_4(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    while left <= right:  # 区间没有变成1个元素,就查找
        middle = left + ((right - left) >> 1)  # 计算中间下标
        if nums[middle] >= target:
            if middle == 0 or nums[middle - 1] < target:  # 关键点
                return middle
            else:  # middle之前肯定还有比target大的元素呢
                right = middle - 1
        else:  # 中间下标比查找的值大,继续在左边查找
            left = middle + 1
    return -1


print(bsearch_4([1, 2, 3, 5, 5, 5, 5, 6, 7], 4))

如果nums[middle]<target,那么肯定要到middle的右侧查找,所以更新left=middle+1。
如果nums[middle]>=target,当middle是0,也就是第一个元素就大于target,那么就返回middle。或者middle前一个元素的值小于target,那么middle就是第一个值大于target的下标,也返回middle。但是如果middle前一个元素的值也大于target,那么middle就不是第一个值大于target的下表,需要到middle的前面继续查找,更新right=middle-1。

7.查找最后一个小于等于给定值的元素

比如有一个数组是[3,4,6,7,10],找到最后一个小于等于5的元素下标。这个问题的解决思路和前面问题的实现思路一致。改造代码:

def bsearch_5(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    while left <= right:  # 区间没有变成1个元素,就查找
        middle = left + ((right - left) >> 1)  # 计算中间下标
        if nums[middle] <= target:
            if middle == len(nums)-1 or nums[middle + 1] > target:  # 关键点
                return middle
            else:  # middle之前肯定还有比target大的元素呢
                left = middle + 1
        else:  # 中间下标比查找的值大,继续在左边查找
            right = middle - 1
    return -1

8. 有序循环数组的二分查找

上面就是二分查找最常用的5种场景,编写二分查找关键是:找到终止条件、更新区间上下界、选择返回值。
如果有序数组是一个循环有序数组,比如 4,5,6,1,2,3。针对这种情况,如何实现一个求“值等于给定值”的二分查找算法呢?这里,假设没重复元素。
如果中间元素正好是待查找元素,那么万事大吉。
如果https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/er-fen-fa-python-dai-ma-java-dai-ma-by-liweiwei141/

def bsearch_6(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    while left <= right:
        middle = left + ((right - left) >> 1)
        if nums[middle] == target:  # 太巧了,中间元素正好是待查找元素
            return middle
        elif nums[left] <= nums[middle]:  # 转折点在右边,左半部分有序,在左半部分进行二分查找,根据情况更新left或者right
            if nums[left] <= target and target < nums[middle]:  # 
                right = middle - 1
            else:
                left = middle + 1
        else:  # 转折点在左边,右半部分有序,在右半部分进行二分查找,根据情况更新left或者right
            if nums[middle] < target and target <= nums[right]:
                left = middle + 1
            else:
                right = middle - 1
    return -1

9. 总结

二分查找是一种非常高效的查找方法,时间复杂度能达到O(logn),也就是说在 42 亿个数据中用二分查找一个数据,最多需要比较 32 次就可以了。
但是二分查找的应用场景比较局限,它只能用在数组这类已经排好序的数据集合中。
在实际应用中,有5种典型问题非常适合二分查找,分别是:

  • 在有序无重复数据的数组中查找等于给定值的元素;
  • 在有序有重复数据的数组中查找第一个值等于给定值的元素;
  • 在有序有重复数据的数组中查找最后一个值等于给定值的元素;
  • 在有序无重复数据的数组中查找第一个大于等于给定值的元素;
  • 在有序无重复数据的数组中查找最后一个小于等于给定值的元素;
    另外,对于循环有序数组也可以用二分法查找。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/liuchunming033/article/details/103420636

智能推荐

PHP将数组存入到数据库中_yii2 如何以数组的形式保存到数据库-程序员宅基地

文章浏览阅读3.7k次。以下四种方法: 1.implode()和explode()方式 2.print_r()和自定义函数方式 3.serialize()和unserialize()方式 4.json_encode()和json_decode()方式// serialize方式function serial($table,$arr){ echo '_yii2 如何以数组的形式保存到数据库

学习OpenCV:rotatedRectangleIntersection计算两个旋转矩形的交集面积-程序员宅基地

文章浏览阅读4.8k次,点赞4次,收藏16次。如图所示,计算两个旋转矩形相交重合区域的顶点,最多返回8个顶点。通过contourArea可返回该顶点集合的面积。void DrawRotatedRect(Mat& imgInoutput, RotatedRect rectInput, Scalar color, int thickness, int lineType){ Point2f* vertices = new cv::Point2f[4]; rectInput.points(vertices); for (int j ._rotatedrectangleintersection

回忆2022:润和软件与openEuler的那些事儿_openeuler commiter-程序员宅基地

文章浏览阅读236次。光阴似箭,我们又来到了岁末盘点时刻,回望2022年,有成长、有收获,更有突破。面对市场变化和疫情防控的双重压力,大家齐心合力,奋发进取,让我们共同回顾润和软件与openEuler之间的辉煌成就!_openeuler commiter

我顺藤摸瓜端了色情网站的老窝,并劝他从良-程序员宅基地

文章浏览阅读2.8k次。感谢凌云给我的启发大家好,我是九歌前几天无意发现了一个色情网站,本着除暴安良的心态,直接开始对这个网站开始了调查这个网站的域名是.cn结尾的 【.cn是国内域名,无法隐藏..._色窝网站

用casperJs phantomJs php 抓取17track订单状态的例子_php 17track api-程序员宅基地

文章浏览阅读3.1k次。php部分:$tracking_number = '148922055008809'; putenv("PHANTOMJS_EXECUTABLE=/usr/local/bin/phantomjs"); $result = shell_exec("casperjs /test/tt.js --tracking_number=".$tracking_number); echo $res_php 17track api

5. 最长回文子串-程序员宅基地

文章浏览阅读102次。给定一个字符串 s,找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。示例 1:输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。示例 2:输入: "cbbd"输出: "bb"解法 1:中心扩散思路很简单:遍历每一个索引,以这个索引为中心,往两边扩散,看最多能扩散多远。具体的做法是利用“回文串”中...

随便推点

Linux下简单的取点阵字模程序_汉字取模linux版-程序员宅基地

文章浏览阅读4.6k次。Linux操作系统下进行简单的图形开发,经常会用到取字模的软件,但是Linux并没有像Windows下的小工具可用,我们也并不希望为了取字模而频繁地切换操作系统。(由于是完全由C语言编写,所以不需要任何修改,这个字库同样可以用在嵌入式环境的Windows操作系统下面)本人结合网上的资料,对这个问题进行了总结,整理了代码,供有需要的朋友使用我参考。转载请注明出处:http://blog.cs_汉字取模linux版

分布式系统sheepdog之dog执行流程_用类图设计dog和penguin类-程序员宅基地

文章浏览阅读1k次。dog部分主要是执行客户端的命令行请求,然后对命令进行解析,通过指定socket发送请求到sheep端,将请求交sheep端处理。具体流程请参考下图。init_commands(&commands)函数将dog支持的命令都初始化在commands中进行调用,包括对vdi、cluster、node的命令操作,setup_commands()函数先比较主命令,然后比较subvommma_用类图设计dog和penguin类

Android 控件右上角角标的实现方案_android 实现符号右上角-程序员宅基地

文章浏览阅读5.9k次,点赞5次,收藏12次。很多项目中都会用到控件的角标,以达到提示作用,如未读信息,剩余量等等,那么如何实现呢?这篇文章将三种方式进行实现,大家按需选择。一、setCompoundDrawblestextView = findViewById(R.id.message_tint);Drawable drawable = getDrawable(R.drawable.red_bubble_bg);..._android 实现符号右上角

银行卡归属地查询 -程序员宅基地

文章浏览阅读4.7k次。业务知识: 本文所有业务知识我已经在《银行卡国内转账、汇款一文通》详细介绍步骤:首先区分借记卡和信用卡,然后就是校验卡号,最后根据银联Bin确定什么银行,Bin之后就是归属地。 本文所有数据来源于网络,不一定保证正确和完整,这里仅仅作为教学使用。 [java] view plaincopypackage org.luozhuang.bankcard; ..._中国银联归属地查询

qt超强精美绘图控件 - QCustomPlot一览 及 安装使用教程_void adddata (const qvector<double > &keys, const -程序员宅基地

文章浏览阅读1k次。1.概述QCustomPlot 是一个超强超小巧的qt绘图类,非常漂亮,非常易用,只需要加入一个qcustomplot.h和qcustomplot.cpp文件即可使用,远比qwt方便和漂亮,可以自己使用两个源文件也可以自己编译成库文件,非常方便。官方网站:http://www.qcustomplot.com/1.0下载地址:http://download.csdn.net/_void adddata (const qvector &keys, const qvector&values)

iOS自动化打包_ios 自动化打包-程序员宅基地

文章浏览阅读1.9k次。参考:iOS自动化打包 ---- xcodebuild 命令详解https://www.jianshu.com/p/770d5df137bfiOS自动化打包 ---- 集成shell脚本https://www.jianshu.com/p/f764249ab9e3_ios 自动化打包

推荐文章

热门文章

相关标签