【二分查找】详细图解_二分查找法流程图-程序员宅基地

技术标签: 图解算法  c语言  二分法  数据结构与算法  

在这里插入图片描述

二分查找

写在前面:

(一)二分法的思想十分容易理解,但是二分法边界处理问题大多数人都是记忆模板,忘记模板后处理边界就一团乱(:“我懂了”, :"你懂个"​)因为我此前也是记忆模板,所以现在想通过一边学习,一边将所学记录成博客教出去(费曼学习法),希望以后能自己推导出边界如何处理,而不仅仅是记忆模板。欢迎一起交流学习,如有看法不一样之处也欢迎留言一起讨论!

(二)我主要解释了二分法的左闭右闭区间,左闭右开区间两种写法,并且每个写法都举了相应的反例,范围写错的话可能会出现的错误等…

1. 简介

故事分享:

有一天小明到图书馆借了 N 本书,出图书馆的时候,警报响了,于是保安把小明拦下,要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下,以找出引发警报的书,但是保安露出不屑的眼神:你连二分查找都不会吗?于是保安把书分成两堆,让第一堆过一下报警器,报警器响;于是再把这堆书分成两堆…… 最终,检测了 logN 次之后,保安成功的找到了那本引起警报的书,露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此,图书馆丢了 N - 1 本书。

保安怎么知道只有一本书没有登记出借,万一全部都没有登记呢​?

这个故事其实说出了二分查找需要的条件

  • 用于查找的内容逻辑上来说是需要有序的
  • 查找的数量只能是一个,而不是多个

比如在一个有序的数组并且无重复元素的数组中,例如[1, 2, 3, 4, 5, 6],需要查找3的位置就可以使用二分查找。

在二分查找中,目标元素的查找区间的定义十分重要,不同的区间的定义写法不一样

因为查找的区间是不断迭代的,所以确定查找的范围十分重要,主要就是左右区间的开和闭的问题,开闭不一样,对应的迭代方式也不一样,有以下两种方式:

  • 左闭右闭[left, right]

  • 左闭右开[left, right)

2. 例子

这是一个使用二分查找的例题

题目如下:

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例一:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例二:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

出自704. 二分查找 - 力扣(LeetCode) (leetcode-cn.com)

二分法的思想很简单,因为整个数组是有序的,数组默认是递增的。

  • 首先选择数组中间的数字和需要查找的目标值比较
  • 如果相等最好,就可以直接返回答案了
  • 如果不相等
    • 如果中间的数字大于目标值,则中间数字向右所有数字都大于目标值,全部排除
    • 如果中间的数字小于目标值,则中间数字向左所有数字都小于目标值,全部排除

二分法就是按照这种方式进行快速排除查找的

tips:

不用去纠结数组的长度是奇数或者偶数的时候,怎么取长度的一半,以下说明,可以跳过。

当数组的长度为奇数的时候

是奇数的情况很简单,指向中间的数字很容易理解,如果需要查找的数字为29

因为29大于中间的数字大于11,所以左边的所有数字全部排除

当数组的长度为偶数的时候

这个时候中间的数字两边的数字数量就不一样了(刚开始学习二分法的时候我经常纠结这个问题,和另外一个长度除2得到的是最中间的数吗的问题,我相信不止我一个人纠结过……但其实这是同一个问题,每次长度除2,如果长度为奇数,得到的中间的数字两边数字数量相同,如果长度为偶数就为上图中间的数字两边的相差为 1)

但是千万不要一直纠结中间的数字两边的数字数量不一样这个问题,因为:

  • 两边数量不一样是一定会出现的情况
  • 但是这种情况并不影响我们对中间数字和目标数字大小关系的判断
    • 只要中间数字大于目标数字,就排除右边的
    • 只要中间数字小于目标数字,就排除左边的

所以数组长度是偶数还是奇数这个真的不重要,不影响怎么排除的问题,无非是多排除一个数字或者少排除一个数字

  • 真正影响的是中间那个数字到底该不该加入下一次的查找中,也就是边界问题

3. 第一种写法(左闭右闭)

二分法最重要的两个点:

  • while循环中 left 和 right 的关系,到底是 left <= right 还是 left < right
  • 迭代过程中 middle 和 right 的关系,到底是 right = middle - 1 还是 right = middle

3.1 正向写法(正确演示)

第一种写法:每次查找的区间在[left, right](左闭右闭区间),根据查找区间的定义(左闭右闭区间),就决定了后续的代码应该怎么写才能对。因为定义 target 在[left, right]区间,所以有如下两点:

  • 循环条件要使用while(left <= right),因为当(left == right)这种情况发生的时候,得到的结果是有意义的
  • if(nums[middle] > target) , right 要赋值为 middle - 1, 因为当前的 nums[middle] 一定不是 target ,需要把这个 middle 位置上面的数字丢弃,那么接下来需要查找范围就是[left, middle - 1]

代码如下:

int search(int nums[], int size, int target) //nums是数组,size是数组的大小,target是需要查找的值
{
    
    int left = 0;
    int right = size - 1;	// 定义了target在左闭右闭的区间内,[left, right]
    while (left <= right) {
    	//当left == right时,区间[left, right]仍然有效
        int middle = left + ((right - left) / 2);//等同于 (left + right) / 2,防止溢出
        if (nums[middle] > target) {
    
            right = middle - 1;	//target在左区间,所以[left, middle - 1]
        } else if (nums[middle] < target) {
    
            left = middle + 1;	//target在右区间,所以[middle + 1, right]
        } else {
    	//既不在左边,也不在右边,那就是找到答案了
            return middle;
        }
    }
    //没有找到目标值
    return -1;
}

下面图解算法的实现过程,建议将代码复制到一个文本编辑器中,边看代码边看图。或者我直接准备了图片,保存下来打开看就好了。

首先看一个数组,需要对这个数组进行操作。需要对33进行查找的操作,那么target 的值就是33

  • 首先,对 left 的值和 right 的值进行初始化,然后计算 middle 的值
    • left = 0, right = size - 1
    • middle = (left + (right - left) / 2 )
  • 比较 nums[middle] 的值和 target 的值大小关系

    • if (nums[middle] > target),代表middle向右所有的数字大于target
    • if (nums[middle] < target),代表middle向左所有的数字小于target
    • 既不大于也不小于就是找到了相等的值
  • nums[middle] = 13 < target = 33,left = middle + 1

  • 见下图:

  • 循环条件为 while (left <= right)

  • 此时,left = 6 <= right = 11,则继续进行循环

  • 当前,middle = left + ((right - left) / 2),计算出 middle 的值

  • 计算出 middle 的值后,比较 nums[middle] 和 target 的值,发现:

    • nums[middle] = 33 == target = 33,找到目标

3.2 反向写法(错误演示)

对应第一种正向的写法,我们把循环条件修改看看会发生什么事

  • 原查找区间 [left, right]
  • 原循环条件是 while (left <= right)

修改后题目对应的条件:

  • 查找区间不变,仍然是[left, right]
  • 查找数字为27 (target = 27)
  • 循环条件修改为while (left < right)

代码:

int search(int nums[], int size, int target) 
{
    
    int left = 0;
    int right = size - 1;	
    while (left < right) {
    	//left <= right 修改为 left < right,其他不变
        int middle = left + ((right - left) / 2);
        if (nums[middle] > target) {
    
            right = middle - 1;
        } else if (nums[middle] < target) {
    
            left = middle + 1;
        } else {
    	
            return middle;
        }
    }
    //没有找到目标值
    return -1;
}

代码图片,边看模拟过程边看代码哦!

好了,现在开始用图片模拟过程

  • 初始化一个数组,计算 middle 的值
  • 根据计算的 middle 值确定 nums[middle]
  • 因为nums[middle] = 13 < target = 27,所以left = middle + 1
  • 继续计算 middle 的值
  • 因为 nums[middle] = 33 > target = 27,所以 right = middle - 1
  • 接着计算 middle 的值
  • 因为 nums[middle] = 22 < target = 27,此时 left = middle + 1,此时 left = right,而循环条件为while (left < right),所以还未找到27 的情况下算法就跳出了循环,返回 -1

4. 第二种写法(左闭右开)

4.1 正向写法(正确演示)

第二种写法:每次查找的区间在 [left, right),(左闭右开区间), 根据区间的定义,条件控制应该如下:

  • 循环条件使用while (left < right)
  • if (nums[middle] > target), right = middle,因为当前的 nums[middle] 是大于 target 的,不符合条件,不能取到 middle,并且区间的定义是 [left, right),刚好区间上的定义就取不到 right, 所以 right 赋值为 middle。

代码如下:

int search(int nums[], int size, int target)
{
    
	int left = 0;
	int right = size; //定义target在左闭右开的区间里,即[left, right)
	while (left < right) {
    	//因为left = right的时候,在[left, right)区间上无意义
		int middle = left + ((right - left) / 2);
		if (nums[middle] > target) {
    
			right = middle; //target 在左区间,在[left, middle)中 
		} else if (nums[middle] < target) {
    
			left = middle + 1;
		} else {
    
			return middle;
		}
	} 
    // 没找到就返回-1
	return -1;
}

代码图片:保存下来边看代码边看图片演示过程

  • 需要查找的值为3

第一步是初始化 left 和 right 的值,然后计算 middle 的值

  • left = 0, right = size
  • 循环条件while (left < right)

因为是左闭右开区间,所以数组定义如下:

  • 计算 middle 的值,
  • 比较 nums[middle] 和 target 的大小:因为 nums[middle] = 22 > target = 3
  • 所以 right = middle
  • 符合循环的条件,接着计算 middle 的值
  • 比较 nums[middle] 和 target 的大小:因为 nums[middle] = 9 > target = 3
  • 所以 right = middle
  • 符合循环的条件,继续计算 middle 的值
  • 比较 nums[middle] 和 target 的大小关系:因为nums[middle] = 0 < target = 3
  • 所以 left = middle + 1

在这里插入图片描述

  • 符合循环条件,接着计算 middle 的值
  • 比较 nums[middle] 和 target 的关系:nums[middle] = 3 == target = 3
  • 成功找到 target

4.2 反向写法(错误演示)

对应第二种正确的写法,照样把循环条件修改,看会发生什么事

正确的写法中条件为:

  • 查找原区间 [left, right)
  • 循环条件为 while (left < right)

修改后题目对应的条件:

  • 查找区间不变,仍然是 [left, right)

  • 循环条件修改为:while (left <= right)

  • 查找的数字为26(数组中不存在这个数字!!!

代码:

int search(int nums[], int size, int target)
{
    
	int left = 0;
	int right = size; 
	while (left <= right) {
    	//条件left < right 修改为 left <= right
		int middle = left + ((right - left) / 2);
		if (nums[middle] > target) {
    
			right = middle; 
		} else if (nums[middle] < target) {
    
			left = middle + 1;
		} else {
    
			return middle;
		}
	} 
    // 没找到就返回-1
	return -1;
}

代码图片:(记得边看边保存图片代码边看图片演示哦!)

以下是演示全过程:

  • 同样,开始初始化一个数组
  • 先计算 middle 的值
  • 判断 nums[middle] 和 target 的大小关系:nums[middle] = 22 < target = 26
  • left = middle + 1 (其实这里nums[left] 已经等于27,26不可能找到,接下去就看算法是否能够知道数组中不存在26并且返回-1 了)
  • 符合循环条件,计算 middle 的值
  • 判断 nums[middle] 和 target 的大小关系:nums[middle] = 57 > target = 26
  • right = middle
  • 满足循环条件,接着计算 middle 的值
  • 比较 nums[middle] 和 target 的大小关系:nums[middle] = 33 > target = 26
  • right = middle
  • 符合循环条件,继续计算 middle 的值
  • 比较 nums[middle] 和 target 大小关系,因为 nums[middle] = 27 > target = 26,
  • 所以 right = middle,自此,left 和 right 相遇,但是循环条件被我们修改成 while (left <= right) 会接着做循环
  • 接下来就是死循环

  • 因为 middle = left + ((right - left) / 2),当 left = right 的时候,middle 的值不会继续改变

  • middle 不继续改变,由于right = middle,right 也不会改变,所以三个数字自此开始不会继续改变

  • 循环条件 while (left <= right) 却仍然满足,不会跳出循环

  • 死循环……

5. 总结

二分法最重要的两个点,就是循环条件和后续的区间赋值问题

因为两者是相互联系,相互影响的,所以就需要两者统一,如果两者不统一,就会出现问题

所以循环条件和赋值问题必须统一,也就是循环不变量。

相关题目推荐:

本文相关信息:

  • 算法学习自微信公众号:“代码随想录”
  • 画图软件:Diagrams
  • 代码生成图片软件:Carbon

️完结撒花️

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_45978890/article/details/116094046

智能推荐

YunCharging充电桩系统开源源码,配套设备+小程序直接商用落地_chargingc公众号-程序员宅基地

文章浏览阅读6k次。​ YunCharging智慧充电系统以微信、公众号为C端主要入口,为充电用户提供查桩找桩、设备信息查询、在线支付、充电状态查询、账户信息等服务,具备在线充值、支付、实时到账功能,给充电用户带来更加安全、便捷、贴心的充电体验。一、付款方式:扫码支付二、产品特点:1、带语音播报功能2、充满自停3、过载保护、漏电保护4、机箱温度监控预警5、4G联网通讯,可远程OTA升级6、收费方式多种:计时、功率段、电量收费7、独立后台管理8、远程主动关闭充电订单9、待机功耗低:低于5W。_chargingc公众号

Vue的生命周期的详解_vue 生命周期-程序员宅基地

文章浏览阅读10w+次,点赞186次,收藏962次。Vue的生命周期Vue的生命周期是每个使用Vue框架的前端人员都需要掌握的知识,以此作为记录。Vue的生命周期就是vue实例从创建到销毁的全过程,也就是new Vue() 开始就是vue生命周期的开始。Vue 实例有⼀个完整的⽣命周期,也就是从开始创建、初始化数据、编译模版、挂载Dom -> 渲染、更新 -> 渲染、卸载 等⼀系列过程,称这是Vue的⽣命周期。钩子函数是Vue生命周期中每个阶段对外开放让程序员操作Vue的接口。Vue有8个钩子函数,分别为:beforeCreate( 创建前_vue 生命周期

【MySQL】如何速通MySQL(1)_mysql速通-程序员宅基地

文章浏览阅读843次,点赞2次,收藏4次。学习Mysql,也就是学习数据库的相关知识,那么到底是啥是数据库啊?数据库是一种用于存储和管理数据的软件系统。它可以通过各种数据结构,如表、索引、视图等方式来组织和存储数据,同时提供方便的数据访问和处理功能,以满足各种业务需求。而对于Mysql,他只是数据库中的其中一种,那么是否需要学习多种数据库呢,答案是否定的。不同的公司或组织可能会使用不同的数据库系统,但通常情况下,掌握一种主流数据库的使用就已经足够了,比如 MySQL、Oracle、SQL Server 等。_mysql速通

mysql两种引擎对比_两种引擎的对比-程序员宅基地

文章浏览阅读189次。对比 myisam innodb 主外键 不支持 支持 事务 不支持 支持 行表锁 表锁,只操作一条数据也会锁表,不适合高并发 行锁,操作时只锁某一行,不对其他操作有影响,适合高并发 缓存 只缓存索引不缓存真是数据 缓存索引与真实数据,对内存性能要要求较高,且内存对性能有决定性影响 表空间 小 大 关注..._两种引擎的对比

Java常用设计模式_常见java设计模式-程序员宅基地

文章浏览阅读212次。最近想简单了解一下设计模式,然后在网上看到了这个专栏,感觉不错,所以转一下参考:专栏:Java常用设计模式_常见java设计模式

5款免费在线软件行为分析(在线沙盘)-程序员宅基地

文章浏览阅读1.8w次。1.Anubis是一个提供可控环境来执行用户提交的二进制文件的动态恶意软件分析平台。该系统通过监视关键的Windows API和系统服务调用、跟踪网络数据流、记录网络通讯,实现对二进制文件的分析,并生成综合分析报告。由于它通过公开的网络接口和很多安全组织、反病毒公司获得恶意程序样本,用户群广泛,所以收集到的样品体现了互联网上广泛而多样的恶意程序。相对于Norman的在线沙盒,来自奥地利的Anu_软件行为分析

随便推点

Python list列表如何删除最大值和最小值并进行相加运算_python删除列表中最大的元素-程序员宅基地

文章浏览阅读1.4w次,点赞9次,收藏39次。首先list列表清除方式有很多,先讲如何删除del 删除值,方法del a[你想要删除数的位置]注:不能 del a 这样写a=[1,2,3,4,5,6,7,8,9,10] #定义列表的值del a[1] #删除a列表中位于第1位的数值,列表从0开始算如a[0--9999]print(a)clear 清空列表a=[1,2,3,4,5,6,7,8,9,10]a.clear()print(a)list1[:]=[]a=[1,2,3,4,5,6,7,8,9,10]a[:] = _python删除列表中最大的元素

谐振回路的选频作用_选频电路的工作原理-程序员宅基地

文章浏览阅读6.9k次,点赞8次,收藏26次。谐振频率时,衰减小,其余衰减大,后级通过幅度比较就把不符合的频率给滤了一、串联电路谐振应用有:1、串联谐振可以用作从众多频率信号中筛选所需信号,利用谐振时电感(或电容)的电压高于外加信号电压的特点,得到高于原信号Q倍的电压再进行放大,在筛选有用信号的同时也抑制了其它频率信号的干扰。2、串联谐振还可以吸收谐振频率的干扰信号,利用谐振时阻抗最小的原理,将LC串联支路并联在电路中,使得谐振频率的信..._选频电路的工作原理

greenplum6集群部署安装_ubuntu greenplum 6 安装配置部署-程序员宅基地

文章浏览阅读1.6k次。greenplum 6 集群部署安装 ,表空间、用户创建,参数优化等_ubuntu greenplum 6 安装配置部署

激活函数的生成及图像_神经网络激活函数图像哪里可以生成-程序员宅基地

文章浏览阅读1.8k次,点赞2次,收藏6次。所谓激活函数(Activation Function),就是在人工神经网络的神经元上运行的函数,负责将神经元的输入映射到输出端。 激活函数(Activation functions)对于人工神经网络模型去学习、理解非常复杂和非线性的函数来说具有十分重要的作用。它们将非线性特性引入到我们的网络中。如下图,在神经元中,输入的 inputs 通过加权,求和后,还被作用了一个函数,这..._神经网络激活函数图像哪里可以生成

win32 masm32 汇编学习 及 远程线程实例_masm32汇编子程序集合-程序员宅基地

文章浏览阅读965次。"门“ 指向某个优先级高的程序所规定的入口点,所有优先级低的程序调用优先级高的程序只能通过门重定向门:中断门,自陷门,任务门。masm32.zipcopy D:\Program Files\Microsoft Visual Studio\VC98\Bin\nmake.exe to ***\masm32\bin相应cmd设置临时环境变量@echo offse_masm32汇编子程序集合

Web前端可视化绘图软件编辑器-汇总_web前端可视化绘图软件编辑器-汇总_前端可视化编辑器_it博客技术分享的博客-csdn-程序员宅基地

文章浏览阅读1.3w次,点赞7次,收藏80次。前言: 随着物联网、大数据等技术高速发展,我们逐步向数字化、可视化的人工智能(AI)时代的方向不断迈进。智能时代是工业 4.0 时代,我国工业领域正努力从“制造”迈向“智造”的新跨越。正文:1.mxgraph:介绍:开源免费,但是需要解决的问题很多,国内学习参考资料少。但是,可视化组态的实现基本都是借助于这个框架来实现的。演示demo:https://jgraph.github.io/mxgraph/javascript/examples/grapheditor/www/index.h..._web前端可视化绘图软件编辑器-汇总_前端可视化编辑器_it博客技术分享的博客-csdn