网站建设推广市场,下载app软件安装到手机,商务网站开发公司,wordpress导航网址文章目录二分查找#xff1a;从基础原理到代码实现二分查找的特点算法重点题目描述#xff1a;LeetCode 704. 二分查找为什么可以用二分查找#xff1f;暴力算法解法二分查找解法核心逻辑#xff1a;三种情况的处理二分查找什么时候结束#xff1f;为什么二分查找一定是对…
文章目录二分查找从基础原理到代码实现二分查找的特点算法重点题目描述LeetCode 704. 二分查找为什么可以用二分查找暴力算法解法二分查找解法核心逻辑三种情况的处理二分查找什么时候结束为什么二分查找一定是对的数学证明单调性下二分查找的有效性数学归纳法时间复杂度代码为什么是二分不是三分、四分细节这些坑别踩快速测试你能找出这些错误吗总结预告朴素二分模板这是封面原图嘿嘿二分查找从基础原理到代码实现
二分查找这个在算法世界里算不上复杂却总让人在细节上栽跟头的算法估计不少人都有过类似经历——明明原理一听就懂上手写却总写出死循环要么就是边界条件处理得一塌糊涂。但只要真正摸透了它的规律就会发现它其实是个“只要学会就简单”的典型今天咱们就借着LeetCode 704.二分查找这道基础题把它的来龙去脉说清楚。 二分查找的特点
为啥二分查找总让人觉得“看着简单写着难”
其实核心就是细节太多 比如这些极易混淆的关键问题稍不注意就会出错
左边界是left还是left1右边界该初始化成nums.size()还是nums.size()-1循环条件用left right还是left right
这些小地方一旦疏忽要么陷入死循环要么出现漏查元素甚至引发越界访问堪称二分查找的“坑点重灾区”。
但它的优点也同样突出尤其是在效率上的碾压性优势
时间复杂度O(log n)对比暴力遍历的O(n)在数据量大时效率天差地别。
举个直观的例子 要在100万个元素中查找一个目标数
暴力遍历最坏情况下需要查100万次二分查找最坏情况下仅需20次因为2^20≈100万。
这也是二分查找能成为面试高频考点的核心原因。
算法重点
1.原理不只是“有序”更是“二段性”
「‼️核心」我们在刚开始接触二分查找的时候经常听说二分查找必须是数组有序的时候才能使用其实这样说会有些片面其中本质不是“有序”而是数组具有 “二段性” 至于什么是二段性简单说就是能找到一个 “判断条件”把数组分成两部分 一部分一定满足条件另一部分一定不满足这样就说这个数组具有二段性
「☝️类比」 比如在书架上找一本《Python编程》书架是按书名首字母排序的。你随便抽一本中间的书比如《Java编程》首字母J发现它在P的左边那你就知道《Python编程》一定在右边——这就是生活中的“二段性”。
回到这道题数组是升序的“判断条件”就可以是“元素是否小于target”左边的元素都小于target右边的元素都大于等于target或者反过来。正是因为有了这种“二段性”我们才能每次拿中间元素和target比然后果断排除左边或右边的一半不用逐个遍历。
2.模板理解逻辑比死记代码重要
二分查找确实有成熟的“模板”但千万别死记硬背——就像手里握着卡塞尔装备部递来的屠龙武器却忘了如何激活、如何瞄准那这把武器反而不如一把普通匕首实用龙族乱入嘿嘿。
常见的二分查找模板主要分为以下三种适用场景各有不同
模板类型核心适用场景特点朴素二分查找查找“唯一存在的目标元素”逻辑最简单上手快但局限性强仅适用于元素无重复的场景本文题目使用的就是该模板查找左边界查找“目标元素第一次出现的位置”适用性更广能处理元素重复的情况细节点更多如边界收缩逻辑查找右边界查找“目标元素最后一次出现的位置”与左边界模板逻辑互补同样适用于重复元素场景是解决复杂查找问题的常用工具
其中后两种模板左边界、右边界查找功能性更万能但涉及的边界处理、循环终止条件等细节也更复杂。咱们明天拆解LeetCode 34题在排序数组中查找元素的第一个和最后一个位置时再逐行梳理这两种模板的逻辑今天的重点是通过LeetCode 704题先把最基础的“朴素二分查找”彻底吃透打好根基。
题目描述LeetCode 704. 二分查找
题目链接二分查找
题目描述 示例 1: 输入: nums [-1,0,3,5,9,12], target 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 示例 2: 输入: nums [-1,0,3,5,9,12], target 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1 提示 1.你可以假设 nums 中的所有元素是不重复的。 2.n 将在 [1, 10000]之间。 3.nums 的每个元素都将在 [-9999, 9999]之间。 为什么可以用二分查找
在讨论二分查找时我们不仅要知道“能用”更要想清楚“为什么用”以及“遇到随机题目时怎么和二分关联”——这才是掌握算法的关键 ✨
我们先看“为什么可以用”二分查找的核心是利用“二段性”缩小范围而这道题恰好完美契合这个前提→题目中的数组是升序排列的。
假设我们随便选数组中间的元素 nums[mid]和目标值 target 对比会立刻出现三种清晰的情况每一种都能帮我们“砍掉”一半无用的查找范围
若 nums[mid] target 直接命中答案不需要再找了直接返回 mid 即可若 nums[mid] target 因为数组是升序的mid 右边所有元素都会比 nums[mid] 更大自然也比 target 大——这半边完全不用看了下次只查 mid 左边若 nums[mid] target 同理mid 左边所有元素都会比 nums[mid] 更小自然也比 target 小——这半边可以直接舍弃下次只查 mid 右边。
之前提到的“二段性”在这里也直接体现出来我们通过 mid 和 target 的大小关系我们能把数组精准分成两部分——一部分是有用的查找范围另一部分是可以直接扔掉的无效范围。
正因为每次都能把查找范围缩小到原来的 1/2二分查找才能实现 O(log n) 的高效时间复杂度这也是它比暴力遍历O(n)强的根本原因
暴力算法解法
既然题目要求O(log n)那肯定不能用暴力但咱们还是先说说暴力解法对比一下就能更直观感受到二分的优势。
暴力解法很简单从头到尾遍历数组逐个比较元素和target。如果找到相等的就返回下标遍历完都没找到就返回-1。代码大概长这样
int search(vectorint nums, int target) {for (int i 0; i nums.size(); i) {if (nums[i] target) {return i;}}return -1;
}这代码肯定能跑通但时间复杂度是O(n)——如果数组有10000个元素最坏情况要循环10000次。现在对两个方法的时间复杂度没有太多概念没有关系后面我们会详细说到
二分查找解法
核心逻辑三种情况的处理
刚才其实已经说了核心思路每次取中间元素mid和target比然后根据结果缩小范围。具体来说
初始化左右边界left 0right nums.size() - 1因为数组下标从0开始最后一个元素下标是size-1循环查找只要left right就证明再合法范围内注意这里是“”后面说原因在这个区间才能继续计算中间下标mid比较nums[mid]和target nums[mid] target找到目标记录下标跳出循环nums[mid] target说明目标在左边把右边界移到mid - 1因为mid已经查过了不用再考虑nums[mid] target说明目标在右边把左边界移到mid 1同理mid不用再考虑 如果循环结束都没找到返回-1。
二分查找什么时候结束
可能有人会想为什么循环条件不能用left right 比如数组只剩一个元素时left和right相等这时候left right不成立循环就结束了那这个元素不就漏查了吗
比如数组[5]target是5初始left0right0left right成立进去计算mid0发现nums[mid]target返回0——正确。
如果target是3数组还是[5]第一次循环mid0nums[mid] target所以rightmid-1-1。这时候left0right-1left right循环结束返回-1——也正确。
为什么二分查找一定是对的
这道题中我们可以明确数组是严格升序排列的单调性极其明确——正是这个特性为二分查找“安全缩小范围”提供了根本保障。
只要数组满足单调性升序或降序通过“中间元素 nums[mid] 与 target 的大小对比”就能精准划分“有效范围”与“无效范围”绝不会出现“漏查目标”的情况
若数组升序nums[mid] target → 右半区所有元素均 target无效可舍弃nums[mid] target → 左半区所有元素均 target无效可舍弃若数组降序逻辑相反但同样能通过一次对比砍掉一半范围。
这种“每次缩小范围都绝对安全”的特性让二分查找最终要么精准定位到目标若存在要么确定目标不存在——不会出现“范围缩错导致漏查”的问题。
数学证明单调性下二分查找的有效性数学归纳法
证明目标对于非空有序数组 nums此处以升序为例若 target 在 nums 中则二分查找必能找到若不在则必能判断不存在。
1. 基础情况n1数组仅1个元素
若 nums[0] target直接返回下标0找到目标若 nums[0] ! target循环结束判断目标不存在。 基础情况成立。
2. 归纳假设假设数组长度为k时结论成立 即对于长度为k的升序数组 nums二分查找能正确判断 target 是否存在存在则返回下标不存在则返回不存在。
3. 归纳递推证明数组长度为k1时结论仍成立 对于长度为k1的升序数组 nums取中间下标 mid left (right - left) // 2避免溢出对比 nums[mid] 与 target
情况1nums[mid] target直接返回mid找到目标结论成立情况2nums[mid] target因数组升序mid 右侧共 (k1)-mid-1 ≤ k 个元素均 target可舍弃剩余查找范围为 [left, mid-1]长度 ≤k。根据归纳假设对长度≤k的数组二分查找能正确判断故结论成立情况3nums[mid] target因数组升序mid 左侧共 mid - left ≤ k 个元素均 target可舍弃剩余查找范围为 [mid1, right]长度 ≤k。同理根据归纳假设结论成立。
综上当数组长度为k1时结论仍成立。
由数学归纳法可知对任意长度的有序数组二分查找的有效性均成立——这也是“单调性”为二分查找提供的数学层面的保障。
时间复杂度
二分查找的核心优势在于每次将查找范围缩小为原来的 1/2这个“减半”过程直到范围为空或找到目标才停止。我们可以通过“查找次数”与“初始范围大小”的对应关系直观看到时间复杂度为何是 O(log n)。
假设初始查找范围包含 n 个元素每次缩小后范围大小如下表所示“第k次查找后”指完成第k轮对比与范围调整后的剩余元素数
查找轮次剩余查找范围大小对应关系以2的幂次表示初始状态nn 2^log₂n第1次后n/2n/2 2^(log₂n - 1)第2次后n/4n/4 2^(log₂n - 2)第3次后n/8n/8 2^(log₂n - 3)………第k次后n/(2^k)n/(2^k) 2^(log₂n - k)终止时≤1n/(2^k) ≤ 1 → 2^k ≥ n
当查找终止时剩余范围大小 ≤1要么找到目标要么确认目标不存在此时满足 n/(2^k) ≤ 1 对不等式变形可得 2^k ≥ n 两边取以2为底的对数log₂根据对数单调性不等号方向不变 k ≥ log₂n 由于查找次数 k 必须是整数因此最多需要 ⌈log₂n⌉ 次查找⌈x⌉ 表示向上取整如 log₂100万≈19.93向上取整为20次。
举个直观例子
当 n100万时log₂100万≈19.93 → 最多只需20次查找当 n10亿时log₂10亿≈29.89 → 最多只需30次查找。 这就是“对数级复杂度”在数据量大时的压倒性优势。
代码
下面是我写的代码结合注释咱们再捋一遍细节
class Solution {
public:int search(vectorint nums, int target) {// 初始化左边界为0右边界为数组最后一个元素的下标int right nums.size() - 1, left 0;// 用于记录结果默认-1没找到int ret -1;// 循环条件left right确保所有可能的位置都查过while (left right) { // 闭区间循环条件别漏了// 计算中间下标用left (right - left)/2代替(leftright)/2避免溢出int middle left (right - left) / 2; // 防溢出别写成(rightleft)/2// 如果中间元素等于target找到目标记录下标并跳出循环if (nums[middle] target) {ret middle;break;}// 如果中间元素大于target说明目标在左边右边界左移到middle-1else if (nums[middle] target) {right middle - 1;}// 如果中间元素小于target说明目标在右边左边界右移到middle1else {left middle 1;}}return ret;}
};这里有个细节必须提计算middle的时候为什么用left (right - left)/2而不是(left right)/2 记住计算mid永远用 left (right - left)/2不用(rightleft)/2两者数学结果相同但前者能避免left和right过大时的整数溢出比如 left2^30 right2^30时rightleft会超INT_MAX。
为什么是二分不是三分、四分
有人可能会想既然二分能缩小一半范围那三分、四分是不是更快理论上每次缩小更多范围次数应该更少
其实不一定。咱们先写个三分查找的例子感受下
// 三分查找示例针对升序数组找target
int ternarySearch(vectorint nums, int target) {int left 0, right nums.size() - 1;while (left right) {// 把范围分成三份找两个中间点int mid1 left (right - left) / 3;int mid2 right - (right - left) / 3;if (nums[mid1] target) return mid1;if (nums[mid2] target) return mid2;// 根据target位置缩小范围if (target nums[mid1]) {right mid1 - 1;} else if (target nums[mid2]) {left mid2 1;} else {left mid1 1;right mid2 - 1;}}return -1;
}四分查找原理类似就是分的段更多中间点更多。
但为什么实际中几乎没人用三分、四分因为
时间复杂度差距不大二分是O(log₂n)三分是O(log₃n)四分是O(log₄n)。但log₂n ≈ 1.58log₃n ≈ 2log₄n差距很小。比如n1e6二分要20次三分只要12次四分只要10次——次数少了但每次循环里的操作变多了三分要算两个中间点判断两次代码复杂度上升分的段越多边界条件越复杂越容易出错维护成本高而且一点选错成本会更高实际效率未必更高虽然次数少但每次循环的计算、判断步骤多整体耗时可能反而比二分更长。
咱们可以写个简单的程序测试下用随机数组多次查找计时
#include iostream
#include vector
#include random
#include chronousing namespace std;// 二分查找
int binarySearch(vectorint nums, int target) {int left 0, right nums.size() - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) return mid;else if (nums[mid] target) right mid - 1;else left mid 1;}return -1;
}// 三分查找
int ternarySearch(vectorint nums, int target) {int left 0, right nums.size() - 1;while (left right) {int mid1 left (right - left) / 3;int mid2 right - (right - left) / 3;if (nums[mid1] target) return mid1;if (nums[mid2] target) return mid2;if (target nums[mid1]) right mid1 - 1;else if (target nums[mid2]) left mid2 1;else {left mid1 1;right mid2 - 1;}}return -1;
}int main() {// 生成一个100万个元素的升序数组int n 1000000;vectorint nums(n);for (int i 0; i n; i) {nums[i] i;}// 随机生成1000个目标值确保在数组范围内random_device rd;mt19937 gen(rd());uniform_int_distribution dist(0, n-1);vectorint targets(1000);for (int i 0; i 1000; i) {targets[i] dist(gen);}// 测试二分查找时间auto start chrono::high_resolution_clock::now();for (int t : targets) {binarySearch(nums, t);}auto end chrono::high_resolution_clock::now();chrono::durationdouble binaryTime end - start;cout 二分查找总时间 binaryTime.count() 秒 endl;// 测试三分查找时间start chrono::high_resolution_clock::now();for (int t : targets) {ternarySearch(nums, t);}end chrono::high_resolution_clock::now();chrono::durationdouble ternaryTime end - start;cout 三分查找总时间 ternaryTime.count() 秒 endl;return 0;
}我跑了几次二分查找总时间大概在0.0002秒左右三分查找大概在0.0004秒左右——反而更慢。所以除非是极特殊的场景否则二分查找是性价比最高的选择大家可以亲自去试一试。
细节这些坑别踩
常见问题正确做法错误案例为什么错右边界初始化right nums.size() - 1right nums.size()可能导致下标越界mid计算left (right - left)/2(leftright)/2left/right过大时溢出循环条件left rightleft right会漏掉leftright时的元素
三个点联动起来记“闭区间初始化右边界取尾下标 安全算 mid 循环到相等”二分查找的边界问题基本就绕不开了
快速测试你能找出这些错误吗
int search(vectorint nums, int target) {int left 0, right nums.size(); while (left right) { int mid (left right) / 2; if (nums[mid] target) return mid;else if (nums[mid] target) right mid - 1;else left mid 1;}return -1;
}答案
right应初始化为nums.size()-1循环条件应是left rightmid计算应是left (right - left)/2 也不算错误就是这种写法更优
总结预告
今天我们从“二段性”这个核心点出发拆解了二分查找的基础逻辑通过LeetCode 704题实现了朴素二分查找的代码也踩了右边界初始化、mid计算溢出这些常见的“坑”。其实二分查找的本质就是“用条件划分范围逐步缩小查找空间”只要抓住这个核心再复杂的变形也能捋清楚。
不过今天的题目里数组元素是“不重复”的所以找到target后直接返回即可。但如果数组里有重复元素比如[1,2,2,3]要找2第一次出现的位置或者最后一次出现的位置朴素二分就不够用了——这就需要用到我们之前提到的“左边界查找”和“右边界查找”模板。
明天要一起研究的是 LeetCode 34题在排序数组中查找元素的第一个和最后一个位置有个小问题可以先想想如果数组是[1,2,2,2,3]target2你觉得“左边界”和“右边界”分别是多少用今天的朴素二分查找能直接找到吗为什么明天我们就用这个例子拆解“左边界查找”的逻辑 “喏Doro给你一朵小花奖励看到这里的你这篇二分查找的拆解有没有把你心里的‘小疑惑’全捋顺呀要是你觉得这篇博客把单调性、二段性这些‘小细节’讲得明明白白就给个点赞鼓励一下嘛~ 要是怕以后找不到这么贴心的讲解可得赶紧收藏起来不然下次遇到二分问题Doro怕你会像Doro一样因为找不到 Orange 时那样‘委屈巴巴’哦~ Doro 知道这个博主后面还会扒更多算法‘小秘密’关注他带你从‘看着会’到‘写得对’再也不被二分的细节‘背刺’啦~最后的最后Doro把这道题的模板写在这里了一定要学会再用哦”
朴素二分模板
while(left right)
{int mid left (right - left)/2;if(.....)//条件left mid 1;else if(.....)//条件right mid -1;elsereturn .....;//找到并返回结果
}
