从三道经典二分题，彻底搞懂「二分查找」的两种核心写法

从三道经典二分题彻底搞懂「二分查找」的两种核心写法二分查找是算法面试的「敲门砖」也是很多人「一看就会一写就废」的重灾区。很多人卡在边界条件、mid计算、循环终止条件上本质是没搞懂二分的两种核心模板。今天我们就通过LeetCode上三道经典二分题彻底拆解二分查找的两种写法帮你彻底吃透这个算法。文章目录从三道经典二分题彻底搞懂「二分查找」的两种核心写法一、先搞懂二分查找的两种核心模板模板1左闭右闭 [left, right]模板2左闭右开 [left, right)模板3向上取整的「找右边界」模板二、题目1x的平方根LeetCode 69题目描述思路分析代码实现逐行注释关键细节拆解三、题目2搜索插入位置LeetCode 35题目描述思路分析代码实现逐行注释关键细节拆解四、题目3山脉数组的峰顶索引LeetCode 852题目描述思路分析代码实现逐行注释关键细节拆解五、三种模板的对比与选型指南选型口诀六、二分查找的避坑指南七、总结一、先搞懂二分查找的两种核心模板二分查找的本质是通过不断缩小搜索区间逼近目标值。根据区间的定义和终止条件我们可以把二分分为两种最常用的模板模板1左闭右闭[left, right]区间定义搜索区间是包含左右端点的闭区间循环条件while (left right)区间收缩当nums[mid] target时目标在右半区left mid 1当nums[mid] target时目标在左半区right mid - 1特点逻辑直观适合「精确查找目标值」的场景模板2左闭右开[left, right)区间定义搜索区间是包含左端点、不包含右端点的半开区间循环条件while (left right)区间收缩当nums[mid] target时目标在右半区left mid 1当nums[mid] target时目标在左半区right mid特点边界处理更统一适合「找满足条件的第一个/最后一个位置」的场景模板3向上取整的「找右边界」模板核心mid left (right - left 1) / 2向上取整循环条件while (left right)适用场景找最后一个满足条件的位置避免死循环区间收缩满足条件时left mid保留mid继续向右找不满足条件时right mid - 1排除mid向左找二、题目1x的平方根LeetCode 69题目描述给你一个非负整数x计算并返回x的 算术平方根 。由于返回类型是整数结果只保留整数部分小数部分将被舍去。注意不允许使用任何内置指数函数和算符例如pow(x, 0.5)或者x ** 0.5。思路分析我们要找的是最大的整数k满足k² ≤ x这是一个典型的「找右边界」问题完美适配向上取整的二分模板。代码实现逐行注释classSolution{public:intmySqrt(intx){// 特殊情况0和1的平方根就是本身直接返回if(x1)return0;// 搜索区间[1, x]因为平方根一定在1到x之间intleft1,rightx;// 循环条件left right当left right时区间收敛到目标值while(leftright){// 核心向上取整计算mid避免死循环// 公式mid left (right - left 1) / 2// 等价于 (left right 1) / 2用前者避免int溢出longlongmidleft(right-left1)/2;// 判断mid的平方是否xif(mid*midx){// 满足条件mid可能是答案保留mid向右继续找更大的kleftmid;}else{// 不满足条件mid太大排除mid向左找rightmid-1;}}// 循环结束时left right就是我们要找的最大kreturnleft;}};关键细节拆解为什么用long long mid当x接近2^31-1时mid*mid会超过int的最大值导致溢出用long long可以安全计算。为什么要向上取整假设left2, right3如果用普通向下取整mid(23)/22当mid*mid x时leftmid2会陷入死循环。向上取整后mid3要么left3跳出循环要么right2跳出循环完美解决死循环问题。为什么最后返回left循环结束时left right这个值就是满足k² ≤x的最大整数也就是我们要的平方根的整数部分。三、题目2搜索插入位置LeetCode 35题目描述给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(log n)的算法。思路分析我们要找的是第一个大于等于target的位置这是一个典型的「找左边界」问题适配左闭右开的二分模板。代码实现逐行注释classSolution{public:intsearchInsert(vectorintnums,inttarget){// 搜索区间[0, nums.size()-1]左闭右闭intleft0,rightnums.size()-1;// 循环条件left right区间收敛到一个元素while(leftright){// 普通向下取整计算mid找左边界用向下取整intmidleft(right-left)/2;if(nums[mid]target){// mid及左边都小于target目标在右半区left右移leftmid1;}else{// mid及右边都大于等于target目标在左半区right左移到midrightmid;}}// 循环结束后left right需要判断最后一个元素是否小于target// 如果小于说明target比所有元素都大插入到末尾left1// 否则left就是第一个target的位置if(nums[left]target)returnleft1;returnleft;}};关键细节拆解为什么最后要加判断当target比数组所有元素都大时循环结束后left right nums.size()-1此时nums[left] target所以插入位置是left1也就是数组末尾。为什么用左闭右开模板这个模板天然适合「找第一个满足条件的位置」边界处理更统一不需要考虑right mid-1的复杂情况。时间复杂度O(log n)每次循环区间缩小一半完美符合题目要求。四、题目3山脉数组的峰顶索引LeetCode 852题目描述符合下列属性的数组arr称为山脉数组arr.length 3存在i0 i arr.length - 1使得arr[0] arr[1] ... arr[i - 1] arr[i]arr[i] arr[i 1] ... arr[arr.length - 1]给你由整数组成的山脉数组arr返回任何满足arr[0] arr[1] ... arr[i - 1] arr[i] arr[i 1] ... arr[arr.length - 1]的下标i。你必须设计并实现时间复杂度为O(log(n))的解决方案。思路分析山脉数组的特点是严格递增到峰顶然后严格递减我们要找的是峰顶的索引也就是「最后一个满足arr[mid] arr[mid-1]的位置」同样是「找右边界」问题用向上取整的二分模板。代码实现逐行注释classSolution{public:intpeakIndexInMountainArray(vectorintarr){// 搜索区间[1, arr.size()-2]// 因为峰顶一定不在0和最后一个位置山脉数组要求0 i arr.length-1intleft1,rightarr.size()-2;// 循环条件left right区间收敛到目标值while(leftright){// 向上取整计算mid避免死循环intmidleft(right-left1)/2;if(arr[mid]arr[mid-1]){// mid在上升区间峰顶在mid或右边保留mid向右找leftmid;}else{// mid在下降区间峰顶在mid左边排除mid向左找rightmid-1;}}// 循环结束时left right就是峰顶的索引returnleft;}};关键细节拆解为什么初始区间是[1, arr.size()-2]山脉数组的峰顶一定不在第一个和最后一个位置所以直接排除这两个位置缩小搜索区间提高效率。为什么用arr[mid] arr[mid-1]作为判断条件对于山脉数组上升区间的元素一定满足arr[mid] arr[mid-1]下降区间的元素一定满足arr[mid] arr[mid-1]用这个条件可以精准判断mid在上升还是下降区间。为什么用向上取整同样是为了避免死循环当left right-1时向上取整会让mid right要么left right跳出循环要么right mid-1 left跳出循环完美解决边界问题。五、三种模板的对比与选型指南看完三道题我们来总结一下三种模板的适用场景帮你快速选型模板类型mid计算方式循环条件核心适用场景典型题目左闭右闭mid left (right - left) / 2while (left right)精确查找目标值普通二分查找左闭右开找左边界mid left (right - left) / 2while (left right)找第一个满足条件的位置搜索插入位置向上取整找右边界mid left (right - left 1) / 2while (left right)找最后一个满足条件的位置x的平方根、山脉数组选型口诀精确查找用闭区间左右边界用开区间找左边界向下取整找右边界向上取整循环结束leftright统一返回left六、二分查找的避坑指南溢出问题永远用mid left (right - left) / 2代替(left right) / 2避免int溢出。死循环问题找右边界时必须用向上取整否则会陷入leftmid的死循环。区间定义一致性整个算法过程中区间的定义必须保持一致不能一会闭区间一会开区间。特殊情况处理一定要处理边界情况比如x0、数组为空、target比所有元素大等。七、总结二分查找的核心不是「代码怎么写」而是「区间怎么定义」。只要搞懂了区间的定义边界条件就迎刃而解了。通过这三道经典题目我们彻底拆解了二分查找的三种核心模板掌握了「找左边界」「找右边界」「精确查找」的写法以后再遇到二分题就能快速选型写出无bug的代码。二分查找是算法的基础也是面试的高频考点吃透这三种模板你就搞定了90%的二分题。