跳到主要内容
二分查找算法详解与实战 | 极客日志
C++ 算法
二分查找算法详解与实战 系统讲解二分查找算法，涵盖朴素二分查找及查找左右边界模板。通过多个力扣算法题（如搜索插入位置、x 的平方根、山峰数组、寻找峰值、旋转排序数组最小值、缺失数字）演示应用场景。重点分析循环条件、中间节点选取策略及防止死循环的细节，提供 C++ 代码实现与复杂度分析，帮助读者掌握二分查找的核心逻辑与实战技巧。
指针猎手 发布于 2026/3/23 更新于 2026/5/3 1. 二分查找算法
在之前的学习当中我们已经初步了解过了二分查找的整体逻辑，接下来我们将系统地学习二分查找的使用方式以及在什么情况下可以使用二分查找。之前了解到的二分查找是要求在有序的数组当中使用，但这只是最朴素的使用场景，接下来我们将学习更多的二分查找应用场景。
1.1 朴素二分查找
704. 二分查找 - 力扣（LeetCode）
通过题目描述可以看出，该算法题要求实现的是在给定的升序数组当中找出指定值 target 的数组下标，如果找不到就返回 -1。
在升序数组当中进行查找可以使用二分查找。创建两个变量 left 和 right 分别指向数组首元素和最后一个元素的下标，创建变量 mid 指向 left 和 right 之间的中间值，再比较 nums[mid] 和指定值 target 的大小：
若 nums[mid] 比 target 大，说明 target 落在 left 到 mid-1 的区间内，将 right 移动到 mid-1 的位置；
若 nums[mid] 比 target 小，说明 target 落在 mid+1 到 right 的区间内，将 left 移动到 mid+1 的位置；
若 nums[mid] 的值等于 target，说明找到目标元素，返回 mid。
一直循环以上操作直到 left 大于 right 就停止。
例如以上示例 1 当中过程如下所示：
代码实现：
class Solution {
public :
int search (vector<int >& nums, int target) int left = 0 , right = nums.size () - 1 ;
while (left <= right) {
int mid = (right + left) / 2
if
1
else
if
1
else
return
return
-1
注： 在以上算法题当中题目的数组长度较短，在计算 mid 时不会出现超出 int 的数据范围的情况。但有时数组的长度较长时使用 mid=(right-left)/2 就会出现超出数据范围的问题，这时就可以使用 mid=left+(right-left)/2 或者 mid=left+(right-left+1)/2，在此只是在个数是偶数时有所差别，使用这两种就不会出现超出数据范围的问题了。
以上就是该算法题的整个解决流程了。接下来我们来学习二分查找当中除了朴素二分查找之外的另外两个模板，分别是查找左边界的二分查找模板和查找右边界的二分查找模板。
1.2 查找左右边界的二分查找 注： 切记在了解以上两种模板过程中不要死记硬背，要理解之后再记忆，否则二分查找就会是最容易写出死循环的算法。
通过题目描述可以看出，该算法题要求实现的是在给定的非递减数组当中找出元素值为 target 的子数组区间，如果原数组当中不存在值为 target 的值就返回区间 [-1, -1]。
题目要求设计出时间复杂度为 O(log n) 的算法，这使得我们无法使用从头暴力遍历数组的方式来实现。虽然可以使用二分查找，但在之前使用二分查找当中数组都是单调递增的，并且查找的是指定元素，而现在需要查找的是一个区间。因此要解决这道题就不能再使用朴素版本的二分查找，而是使用查找左区间和右区间的二分查找。
其实以上两个改进的二分查找也是基于朴素的二分查找实现的，只不过在查找时改变了查找的策略。在此使用二分查找就只需要给定的数据具有二段性即可。
查找左端点时：
此时如果 nums[mid] 的值是小于 target 的，这就说明此时的 mid 落在元素值<target 的区间内。由于最后我们是要找出值为 target 的区间，因此最后区间内的所有元素值都是等于 target 的，那么 nums[mid] 落在元素值小于 target 的区间就说明从 left 到 mid 的值都是小于 target 的，都不满足要求，这时就可以将 left 移动到 mid 之后一位，也就是 left=mid+1。
查找右端点时：
此时如果 nums[mid] 的值是大于 target 的，这就说明此时的 mid 落在元素值>target 的区间内。由于最后我们是要找出值为 target 的区间，因此最后区间内的所有元素值都是等于 target 的，那么 nums[mid] 落在元素值大于 target 的区间就说明此时 mid 位置的值有可能满足要求的，所以这时就可以将 right 移动到 mid 的位置，也就是 right=mid。
循环结束条件分析：
在寻找左右端点的过程当中，循环的结束条件以及求中间节点的操作有两个重要的细节问题。
我们知道在查找左区间的端点时会有能找到端点在 left 和 right 之间，还有给定的数据值都是小于 target 的，最后一种是给定的数据全部都是大于 target 的。在这以上三种情况当中都是当 left 都等于 right 就不需要再进行判断了，并且在情况一和情况三当中如果将循环条件定为 left<=right，由于进行的操作是 right=mid，这时就会出现死循环。
因此综上所述寻找区间左端点时的循环结束条件要定为 left<right。原因有两点：
left=right 时，此时 left 或者 right 指向的下标就是结果，无需判断。
若进行 left=right 的判断就会在一些场景下出现死循环。
寻找右区间的端点的循环条件的分析与以上左端点类似，右端点时的循环结束条件也要定为 left<right。
中间节点的选取限制：
在选择中间节点计算有两种分别是 mid=left+(right-left)/2 和 mid=right+(right-left+1)/2，在此这两种只是在数据个数是偶数时有区别。
先来分析左端点：
在寻找区间的左端点时如果只有两个数据时如果第二个数据值是等于 target 的，那么来依次分析使用 mid=left+(right-left)/2 和 mid=right+(right-left+1)/2 是否都符合要求。
如果是使用 mid=left+(right-left)/2 就可以得出 mid 指向 1，那么再进入循环就会将 left 移动到 mid+1 也就是 right 的位置，此时之后 left=right，最终是符合要求的。
如果是使用 mid=left+(right-left+1)/2 就可以得出 mid 指向 2，那么再进入循环就会一直让 right=mid，此时就会造成死循环，最终是不符合要求的。
因此综上就可以得出在求区间的左端点时中间下标要使用 mid=left+(right-left)/2。
接下来分析右端点：
在寻找区间的右端点时如果只有两个数据时如果第一个数据值是等于 target 的，那么来依次分析使用 mid=left+(right-left)/2 和 mid=right+(right-left+1)/2 是否都符合要求。
如果是使用 mid=left+(right-left)/2 就可以得出 mid 指向 1，那么再进入循环就会一直让 left=mid，此时就会造成死循环，最终是不符合要求的。
如果是使用 mid=left+(right-left+1)/2 就可以得出 mid 指向 2，那么再进入循环就会将 right 移动到 mid-1 也就是 left 的位置，此时之后 left=right，最终是符合要求的。
因此综上就可以得出在求区间的右端点时中间下标要使用 mid=left+(right-left+1)/2。
完成以上两个细节的分析接下来我们就来试着实现该算法题的代码：
class Solution {
public :
vector<int > searchRange (vector<int >& nums, int target) {
if (nums.size () == 0 ) return {-1 , -1 };
int left = 0 , right = nums.size () - 1 ;
while (left < right) {
int mid = left + (right - left) / 2 ;
if (nums[mid] < target) left = mid + 1 ;
else right = mid;
}
int begin = left;
left = 0 , right = nums.size () - 1 ;
while (left < right) {
int mid = left + (right - left + 1 ) / 2 ;
if (nums[mid] > target) right = mid - 1 ;
else left = mid;
}
int end = left;
if (nums[begin] != target) return {-1 , -1 };
else return {begin, end};
}
};
总结模板 将以上的查找区间左和右端点的步骤总结就可以得出以下的模板。
在此切记不要死记模板，大家一定不要觉得背下模板就能解决所有二分问题。二分问题最重要的就是要分析题意，然后确定要搜索的区间，根据分析问题来写出二分查找算法的代码。
在此你只要记住的是当 if……else 语句当中出现 mid-1 时就要将确定中间下标 mid 写成 mid=left+(right-left+1)/2。
2. 二分查找算法题练习 接下来我们会通过几道算法题来巩固之前学习的二分查找算法，并且每道题都会以题目解析、算法原理讲解、代码实现三步带你完全理解每道算法题。
2.1 搜索插入位置
题目解析 通过题目描述可以看出该算法题要求实现的是在找到目标值为 target 的元素下标，并且当在数组当中找不到对应元素时就要找出该值插入到数组当中使数组依然保持升序的数组下标。
算法原理讲解 在该算法题当中要求我们使用 O(log n) 的算法效率来实现，这使得我们不能使用暴力遍历数组来实现。在这道题当中其实我们可以将数组分为两个部分，一部分是小于给定值 target 的，另一部分是大于指定值 target 的部分。
那么这时就说明给定的数组是拥有二段性的，这时就可以使用二分查找算法来实现。当数组当中存在指定值 target 时就最终查找完毕就返回的是值为 target 元素的下标，如果数组当中不存在值为 target 的值最终就返回的是比 target 值大的元素的值，这时恰巧就是之后要将值为 target 的元素插入的位置。
以上的情况我们使用一个查找左区间的二分查找就可以实现了，但有一种特殊情况需要我们单独处理一下，那就是当数组当中不存在值为 target 的值，并且若要插入 target 的值最终是插到数组的末尾，这时二分查找的结果是数组的最后一个元素的下标就不符合要求。这种情况的特点其实就是 target>nums[left]，那么就只需要在二分查找之后进行判断如果满足条件就返回 left+1 的值。
代码实现 class Solution {
public :
int searchInsert (vector<int >& nums, int target) int left = 0 , right = nums.size () - 1 ;
while (left < right) {
int mid = left + (right - left) / 2 ;
if (nums[mid] < target) left = mid + 1 ;
else right = mid;
}
if (target > nums[left]) return left + 1 ;
return left;
}
};
2.2 x 的平方根
题目解析 在这道算法题当中题目给定了我们一个非负整数 x，我们需要找出这个整数的算术平方根，如果得到的平方根不是整数就只需要将整数部分返回，小数部分去掉。
算法原理讲解 在这道题当中题目要求我们不能使用内置指数函数 pow, sqrt 等，那么这时我们就要想着如何使用其他的方式来实现了。
最容易想到的方法是从 1 开始到 x 判断对应的数平方是不是等于 x，是的话就返回此时的值，如果出现此时的平方值大于 x 就返回此时的值减一的值。并且在这些步骤的最开始就判断 x 的值是否是等于 0，是的话就直接返回 0。
除了以上的解法还有什么更好的算法呢？从 1 到 x 的数字的平方其实可以分为两个部分，就是平方值小于等于 x 的值和平方值大于 x 的值。
那么这时我们不就是要查找右区间吗？因此这时就可以使用查找右区间的二分查找算法来实现，创建两个变量 left 和 right 分别初始化为 1 和 x，创建 mid 变量存储中间值下标，之后当 mid 平方大于 x 时就将 right 移到 mid 的位置，当 mid 平方的值小于等于 x 的值就将 left 移动到 mid-1 的位置，最后重复以上的操作最后 left 或者 right 的值就是要返回的值。
代码实现 class Solution {
public :
int mySqrt (int x) if (x == 0 ) return 0 ;
long long begin = 1 , end = x;
while (begin <= end) {
if (begin * begin == x) {
return begin;
} else if (begin * begin > x) {
return begin - 1 ;
}
begin++;
}
return -1 ;
}
};
class Solution {
public :
int mySqrt (int x) if (x == 0 ) return 0 ;
int left = 1 , right = x;
while (left < right) {
long long mid = left + (right - left + 1 ) / 2 ;
if ((mid * mid) > x) right = mid - 1 ;
else left = mid;
}
return left;
}
};
2.3 山峰数组的峰顶索引
题目解析 通过题目描述可以看出该算法题要求实现的是从数组当中找出峰值元素，也就该元素比其左边的元素大，比其右边的元素小，并且题目给定的数组长度最小为 3，保证会有峰值元素。
算法原理讲解 在此题目要求我们实现出时间复杂度为 O(log n) 的算法，这使得我们不能使用遍历数组来实现。要求 O(log n) 的算法，那就试着看能不能使用二分查找来实现，这时就要看数组当中是否具有二段性。
在此是可以看出给定的数组是具有二段性的，数组的左半部分的元素前面的元素值都小于后面元素的值；数组的右半部分的元素前面的元素的值都大于后面的元素值。
因此要实现这道算法题其实只需在数组当中查找左边元素大于右边元素的左区间，这时最终循环结束的适合 left 指向的下标就是我们想要的值。
代码实现 class Solution {
public :
int peakIndexInMountainArray (vector<int >& arr) int left = 0 , right = arr.size () - 1 ;
while (left < right) {
int mid = left + (right - left) / 2 ;
if (arr[mid] < arr[mid + 1 ]) left = mid + 1 ;
else right = mid;
}
return left;
}
};
2.4 寻找峰值
题目解析 通过题目描述可以看出该算法题要求我们从给定的数组当中找出峰值元素的下标，在数组当中有可能有多个元素都是峰值元素；那么这时我们只需要找出一个符合要求的峰值元素下标即可。并且题目中还规定 nums[-1]=0, nums[n]=-∞，这就可以使得数组即使是只有一个元素时也是有峰值的。
算法原理讲解 在以上算法题当中要求使用 O(log n) 效率的时间复杂度解决，那么这时我们就要看看给定的数组是否有二段性，有的话就可以试着使用二分查找算法来解决。
由于给定的数组是有多个峰值元素的，因此在该数组当中我们就可以将其划分为两个区间；分别是左元素值大于右元素值得区间，和左元素值小于右元素值得区间，这时就说明数组是有二段性的。
代码实现 class Solution {
public :
int findPeakElement (vector<int >& nums) if (nums.size () == 1 ) return 0 ;
int left = 0 , right = nums.size () - 1 ;
while (left < right) {
int mid = left + (right - left) / 2 ;
if (nums[mid] < nums[mid + 1 ]) left = mid + 1 ;
else right = mid;
}
return left;
}
};
2.5 搜索旋转排序数组中的最小值
题目解析 通过题目描述可以看出该算法题要求实现的是在给定的经过多次旋转之后是升序的数组当中找出值最小的元素。
算法原理讲解 在此你看到这道算法题的第一想法就是将给定的数组旋转之后变回升序这样数组的第一个元素就是最小的元素，但是题目要求用 O(log n) 的时间复杂度来解决，以上这种算法当数组一开始是逆序的时候时间复杂度为 O(n)，这就不符合我们的要求了，因此我们要再想想其他的算法。
在此我们来观察数组是否有二段性，因此来判断是否能使用二分查找。
在此如果数组不是一开始就是升序情况时，是可以将数组划分为以下两个区间的，两个区间内的数组元素都是升序的。
通过图像我们可以发现，[A, B] 区间内的点都是严格大于 D 点的值的，C 点的值是严格小于 D 点的值的。但是当 [C, D] 区间只有一个元素的时候，C 点的值是可能等于 D 点的值的。
因此一以上就根据元素的值是否大于数组最后一个元素的值将其划分为两个区间，这样数组就具有二段性，就可以使用二分查找算法。
那么就可以使用查找左端点的二分查找算法来实现，一开始就判断数组当中的最后一个元素是否大于数组的首元素，是的话就说明数组已经有序就直接返回数组的首元素即可。初始化两个变量 left 和 right；两个变量分别初始化为 0 和 nums.size()-1，之后创建表示中间值下标的变量 mid，之后进行判断当 nums[mid]>数组最后一个元素时就将 left 移动到 mid+1 的位置否则就将 right 移动到 mid 的位置。一直重复以上操作直到 left 等于 right 此时 left 下标指向的数组元素就是数组当中的最小值。
代码实现 class Solution {
public :
int findMin (vector<int >& nums) int n = nums.size ();
if (nums[0 ] < nums[n - 1 ]) return nums[0 ];
int left = 0 , right = n - 1 ;
while (left < right) {
int mid = left + (right - left) / 2 ;
if (nums[mid] > nums[n - 1 ]) left = mid + 1 ;
else right = mid;
}
return nums[left];
}
};
2.6 0~n-1 中缺失的数字
题目解析 以上的题目的要求很简单；就是要从 n 个元素的数组当中找出 0~n-1 缺失的元素。
算法原理讲解 在此算法题很简单就好想到的算法就是直接遍历数组，当数组下标和对应下标的元素不相等时就返回此时的下标，但这种算法的时间复杂度为 O(n)，还有什么更好的算法呢？
在此其实我们是可以根据数组元素的值是否与其下标相等将数组划分为两个区间。
那么在此就可以使用查找左区间的二分查找算法来解决该算法题。
代码实现 class Solution {
public :
int takeAttendance (vector<int >& records) for (int i = 0 ; i < records.size (); i++) {
if (records[i] != i) return i;
}
return records.size ();
}
};
class Solution {
public :
int takeAttendance (vector<int >& records) int left = 0 , right = records.size () - 1 ;
while (left < right) {
int mid = left + (right - left) / 2 ;
if (records[mid] == mid) left = mid + 1 ;
else right = mid;
}
if (records[left] == left) left++;
return left;
}
};
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Gemini 图片去水印 基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown转HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
