二分查找：一种经典的 O(log n) 高效搜索算法
在算法学习中，二分查找是一个非常经典、非常重要的基础算法。它常用于在有序数组中快速查找某个目标值的位置。
相比于普通的线性查找，二分查找的效率非常高。线性查找需要从头到尾一个一个遍历，时间复杂度是 O(n)；而二分查找每次都会排除一半的搜索区间，因此时间复杂度可以达到 O(log n)。
本文将结合一道经典题目：
在排序数组中查找元素的第一个和最后一个位置
来系统讲解二分查找的思想、代码实现以及边界处理方法。
一、什么是二分查找？
二分查找，也叫折半查找。
它的核心思想是：
在一个有序数组中，每次取中间位置的元素与目标值比较，根据比较结果缩小一半搜索范围。
假设数组是升序排列的：
nums = [5, 7, 7, 8, 8, 10] target = 8我们想查找8的位置。
普通查找可能要从下标0开始一个一个看：
5 -> 7 -> 7 -> 8而二分查找会先看中间元素，然后判断目标值在左半部分还是右半部分。
这种方法每次都能排除一半数据，因此非常高效。
二、二分查找为什么是 O(log n)？
假设数组长度为 n。
第一次查找后，范围变成：
n / 2第二次查找后，范围变成：
n / 4第三次查找后，范围变成：
n / 8不断折半，直到搜索范围缩小为 1。
也就是说，我们需要找到一个 k，使得：
n / 2^k = 1变形可得：
2^k = n因此：
k = log₂n所以二分查找的时间复杂度是：
O(log n)举个例子，如果数组有 100 万个元素，线性查找最坏可能要查找 100 万次，而二分查找大约只需要：
log₂1000000 ≈ 20也就是说，最多查找 20 次左右就能完成。
这就是二分查找高效的原因。
三、二分查找的基本模板
普通二分查找用于查找目标值是否存在，或者返回目标值的任意一个位置。
代码如下：
int binarySearch(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }这里有一个细节：
int mid = left + (right - left) / 2;不要直接写成：
int mid = (left + right) / 2;因为当left和right都很大时，left + right可能会发生整数溢出。
所以更安全的写法是：
left + (right - left) / 2四、题目分析：查找第一个和最后一个位置
题目要求：
给定一个升序排列的整数数组nums，和一个目标值target，找出目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值，返回：
[-1, -1]示例：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]因为8第一次出现的位置是下标3，最后一次出现的位置是下标4。
再看一个例子：
输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]因为数组中没有6。
五、为什么不能只用普通二分查找？
普通二分查找只能找到目标值的某一个位置。
比如：
nums = [5, 7, 7, 8, 8, 10] target = 8普通二分查找可能找到下标3，也可能找到下标4，但题目要求我们找到：
第一个 8 的位置：3 最后一个 8 的位置：4所以我们需要对二分查找进行改造。
思路是：
用一次二分查找，寻找 target 的最左位置。
再用一次二分查找，寻找 target 的最右位置。
六、寻找左边界
寻找左边界时，如果nums[mid] == target，不能立即返回。
因为当前的mid虽然是 target，但它不一定是第一个 target。
例如：
nums = [5, 7, 7, 8, 8, 10]当我们找到下标4的8时，左边下标3仍然也是8。
所以我们应该记录当前答案，然后继续向左搜索。
核心代码：
if (nums[mid] == target) { result = mid; right = mid - 1; }完整代码如下：
int findLeft(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; }这段代码的关键是：
result = mid; right = mid - 1;它表示：
虽然已经找到了一个 target，但是还要继续往左边找，看看有没有更靠前的位置。
七、寻找右边界
寻找右边界和寻找左边界类似。
区别在于，当nums[mid] == target时，我们要继续向右搜索。
核心代码：
if (nums[mid] == target) { result = mid; left = mid + 1; }完整代码如下：
int findRight(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; left = mid + 1; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; }这段代码的关键是：
result = mid; left = mid + 1;它表示：
虽然已经找到了一个 target，但是还要继续往右边找，看看有没有更靠后的位置。
八、完整代码实现
#include <iostream> #include <vector> using namespace std; class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int left = findLeft(nums, target); int right = findRight(nums, target); return {left, right}; } private: int findLeft(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } int findRight(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; left = mid + 1; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } };九、代码执行过程分析
以数组：
nums = [5, 7, 7, 8, 8, 10] target = 8为例。
寻找左边界时：
第一次：
left = 0 right = 5 mid = 2 nums[mid] = 7因为7 < 8，所以目标值在右边：
left = mid + 1 = 3第二次：
left = 3 right = 5 mid = 4 nums[mid] = 8找到 target，记录：
result = 4但还要继续向左找：
right = mid - 1 = 3第三次：
left = 3 right = 3 mid = 3 nums[mid] = 8再次找到 target，更新：
result = 3继续向左找：
right = mid - 1 = 2此时：
left = 3 right = 2循环结束，左边界为：
3同理，寻找右边界时最终会得到：
4所以最终结果是：
[3, 4]十、复杂度分析
这道题中，我们进行了两次二分查找。
第一次查找左边界，时间复杂度是：
O(log n)第二次查找右边界，时间复杂度也是：
O(log n)所以总时间复杂度为：
O(log n) + O(log n) = O(log n)空间复杂度方面，只使用了几个变量：
left、right、mid、result没有使用额外数组，因此空间复杂度为：
O(1)最终复杂度：
时间复杂度：O(log n) 空间复杂度：O(1)十一、二分查找的适用条件
二分查找虽然高效，但不是所有情况都能使用。
它通常需要满足以下条件：
1. 数据必须具有单调性
最常见的情况是数组已经排序。
例如：
[1, 3, 5, 7, 9]这种数组可以使用二分查找。
但是如果数组是无序的：
[5, 1, 9, 3, 7]普通二分查找就不能直接使用。
2. 可以通过中间值判断搜索方向
二分查找的关键是：
通过nums[mid]和target的比较，判断下一步应该去左边还是右边。
如果不能判断方向，就无法排除一半数据。
十二、二分查找常见错误
1. 循环条件写错
常见写法有两种：
while (left <= right)和：
while (left < right)这两种写法都可以，但边界更新方式不同。
本文使用的是：
while (left <= right)它表示搜索区间是闭区间：
[left, right]也就是说，left和right指向的位置都可能是答案。
2. mid 计算可能溢出
不推荐写法：
int mid = (left + right) / 2;推荐写法：
int mid = left + (right - left) / 2;这样可以避免整数溢出。
3. 找到 target 后直接返回
在普通二分查找中，找到 target 可以直接返回。
但是在这道题中不行。
因为题目要求的是 target 的第一个和最后一个位置。
所以找到 target 后还要继续搜索：
寻找左边界：
right = mid - 1;寻找右边界：
left = mid + 1;十三、总结
二分查找是一种非常经典的高效搜索算法。
它的核心思想是：
利用有序性，每次排除一半搜索空间。
在普通查找中，时间复杂度是 O(n)；而二分查找可以将复杂度优化到 O(log n)。
本文讲解的这道题并不是简单地判断目标值是否存在，而是要求查找目标值的左右边界。因此，我们需要对普通二分查找进行改造：
findLeft(nums, target)用于查找第一个出现的位置；
findRight(nums, target)用于查找最后一个出现的位置。
最终代码的时间复杂度为：
O(log n)空间复杂度为：
O(1)二分查找虽然代码不长，但边界处理非常重要。只要能够理解搜索区间、循环条件和左右边界更新方式，就可以解决大量与有序数组相关的问题。
对于算法学习来说，二分查找是必须掌握的基础内容，也是后续学习查找优化、答案二分、旋转数组搜索等问题的重要基础。