在算法学习中二分查找是一个非常经典、非常重要的基础算法。它常用于在有序数组中快速查找某个目标值的位置。相比于普通的线性查找二分查找的效率非常高。线性查找需要从头到尾一个一个遍历时间复杂度是 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(vectorint 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(vectorint 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(vectorint 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: vectorint searchRange(vectorint nums, int target) { int left findLeft(nums, target); int right findRight(nums, target); return {left, right}; } private: int findLeft(vectorint 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(vectorint 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)二分查找虽然代码不长但边界处理非常重要。只要能够理解搜索区间、循环条件和左右边界更新方式就可以解决大量与有序数组相关的问题。对于算法学习来说二分查找是必须掌握的基础内容也是后续学习查找优化、答案二分、旋转数组搜索等问题的重要基础。
