二分查找是高效解决有序/局部有序数组问题的经典算法，核心思想是通过不断缩小“可能包含目标的区间”，将时间复杂度从暴力遍历的O(n)O(n)O(n)优化到O(logn)O(\log n)O(logn)。
它的适用场景非常广泛：不仅能解决“查找目标值”这类基础问题，还能处理“找边界”“找极值”“旋转数组”等复杂场景。本文将通过7道经典题目，拆解二分查找在不同场景下的解题思路与代码实现。
一、在排序数组中查找元素的第一个和最后一个位置
题目描述：
给定非递减排序的整数数组nums和目标值target，找出target在数组中的开始位置和结束位置；若不存在则返回[-1, -1]。要求时间复杂度为O(logn)O(\log n)O(logn)。
示例：
- 输入：
nums = [5,7,7,8,8,10], target = 8，输出：[3,4] - 输入：
nums = [5,7,7,8,8,10], target = 6，输出：[-1,-1]
解题思路：
通过两次二分查找分别确定左边界和右边界：
- 找左边界：二分找第一个等于
target的位置。若nums[mid] < target，左指针右移；否则右指针左移，最终左指针即为左边界。 - 找右边界：二分找最后一个等于
target的位置。若nums[mid] <= target，左指针右移；否则右指针左移，最终右指针即为右边界。 - 若左边界对应的元素不是
target，直接返回[-1,-1]。
完整代码：
classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){if(nums.size()==0)return{-1,-1};intbegin=0;intleft=0,right=nums.size()-1;// 找左边界while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}if(nums[left]!=target)return{-1,-1};elsebegin=left;// 找右边界right=nums.size()-1;while(left<right){intmid=left+(right-left+1)/2;if(nums[mid]<=target)left=mid;elseright=mid-1;}return{begin,right};}};复杂度分析：
- 时间复杂度：O(logn)O(\log n)O(logn)，两次二分查找各占O(logn)O(\log n)O(logn)。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
二、x 的平方根
题目描述：
给定非负整数x，计算并返回其算术平方根的整数部分（舍去小数部分），不允许使用内置指数函数或运算符。
示例：
- 输入：
x = 4，输出：2 - 输入：
x = 8，输出：2（8的平方根是2.828…，取整数部分）
解题思路：
通过二分查找找最大的整数mid，使得mid² <= x：
- 边界条件：若
x < 1，直接返回0；否则二分区间为[1, x]。 - 二分过程：计算
mid = left + (right - left + 1) / 2（避免死循环），用long long存储mid * mid防止整数溢出；若mid * mid <= x，左指针右移（保留当前候选值），否则右指针左移。
完整代码：
classSolution{public:intmySqrt(intx){if(x<1)return0;intleft=1,right=x;while(left<right){longlongmid=left+(right-left+1)/2;if(mid*mid<=x)left=mid;elseright=mid-1;}returnleft;}};复杂度分析：
- 时间复杂度：O(logx)O(\log x)O(logx)，二分区间大小为
x，每次缩小一半。 - 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
三、搜索插入位置
题目描述：
给定排序数组nums和目标值target，找到target在数组中的索引；若不存在，则返回其按顺序插入的位置。要求时间复杂度为O(logn)O(\log n)O(logn)。
示例：
- 输入：
nums = [1,3,5,6], target = 5，输出：2 - 输入：
nums = [1,3,5,6], target = 2，输出：1
解题思路：
通过二分查找找第一个大于等于target的位置：
- 若
nums[mid] < target，说明target在右边，左指针右移；否则右指针左移。 - 最终左指针即为目标位置（若
nums[left] < target，则插入到left+1，否则插入到left）。
完整代码：
classSolution{public:intsearchInsert(vector<int>&nums,inttarget){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]<target)left=mid+1;elseright=mid;}returnnums[left]<target?left+1:left;}};复杂度分析：
- 时间复杂度：O(logn)O(\log n)O(logn)，二分遍历数组。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
四、山脉数组的峰顶索引
题目描述：
给定山脉数组arr（先递增后递减），返回峰值元素的下标，要求时间复杂度为O(logn)O(\log n)O(logn)。
示例：
- 输入：
arr = [0,1,0]，输出：1 - 输入：
arr = [0,2,1,0]，输出：1
解题思路：
山脉数组的峰值满足arr[mid] > arr[mid-1]且arr[mid] > arr[mid+1]，通过二分缩小范围：
- 二分区间为
[1, arr.size()-2]（避免越界），比较arr[mid]和arr[mid-1]：- 若
arr[mid] > arr[mid-1]，说明峰值在右边，左指针右移。 - 否则说明峰值在左边，右指针左移。
- 若
- 最终左指针即为峰值下标。
完整代码：
classSolution{public:intpeakIndexInMountainArray(vector<int>&arr){intleft=1,right=arr.size()-2;while(left<right){intmid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1])left=mid;elseright=mid-1;}returnleft;}};复杂度分析：
- 时间复杂度：O(logn)O(\log n)O(logn)，二分遍历数组。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
五、寻找峰值
题目描述：
峰值元素是指严格大于左右相邻值的元素，给定数组nums，返回任意一个峰值的下标。假设nums[-1] = nums[n] = -∞，要求时间复杂度为O(logn)O(\log n)O(logn)。
示例：
- 输入：
nums = [1,2,3,1]，输出：2 - 输入：
nums = [1,2,1,3,5,6,4]，输出：1或5
解题思路：
利用“边界为负无穷”的假设，通过二分找峰值：
- 二分区间为
[0, nums.size()-1]，比较nums[mid]和nums[mid+1]：- 若
nums[mid] > nums[mid+1]，说明峰值在左边（包括mid），右指针左移。 - 否则说明峰值在右边，左指针右移。
- 若
- 最终左指针即为峰值下标（必然存在峰值）。
完整代码：
classSolution{public:intfindPeakElement(vector<int>&nums){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]>nums[mid+1])right=mid;elseleft=mid+1;}returnleft;}};复杂度分析：
- 时间复杂度：O(logn)O(\log n)O(logn)，二分遍历数组。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
六、寻找旋转排序数组中的最小值
题目描述：
给定升序旋转后的数组nums（元素互不相同），返回数组中的最小元素，要求时间复杂度为O(logn)O(\log n)O(logn)。
示例：
- 输入：
nums = [3,4,5,1,2]，输出：1 - 输入：
nums = [4,5,6,7,0,1,2]，输出：0
解题思路：
旋转后的数组分为“左升序段”和“右升序段”，最小值是右段的第一个元素：
- 二分区间为
[0, nums.size()-1]，比较nums[mid]和nums.back()（最后一个元素）：- 若
nums[mid] > nums.back()，说明mid在左段，最小值在右边，左指针右移。 - 否则说明
mid在右段，最小值在左边（包括mid），右指针左移。
- 若
- 最终左指针即为最小值的下标。
完整代码：
classSolution{public:intfindMin(vector<int>&nums){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mid]>nums[nums.size()-1])left=mid+1;elseright=mid;}returnnums[left];}};复杂度分析：
- 时间复杂度：O(logn)O(\log n)O(logn)，二分遍历数组。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
七、点名
题目描述：
班级n位同学的学号为0~n-1，点名结果记录于升序数组records，仅一位同学缺席，返回其学号。
示例：
- 输入：
records = [0,1,2,3,5]，输出：4 - 输入：
records = [0,1,2,3,4,5,6,8]，输出：7
解题思路：
正常情况下records[mid] == mid，缺席的学号会打破该关系：
- 二分区间为
[0, records.size()-1]，比较records[mid]和mid：- 若
records[mid] == mid，说明缺席在右边，左指针右移。 - 否则说明缺席在左边（包括
mid），右指针左移。
- 若
- 最终若
records[left] == left，缺席学号为left+1；否则为left。
完整代码：
classSolution{public:inttakeAttendance(vector<int>&records){intleft=0,right=records.size()-1;while(left<right){intmid=left+(right-left)/2;if(records[mid]==mid)left=mid+1;elseright=mid;}returnrecords[left]==left?left+1:left;}};复杂度分析：
- 时间复杂度：O(logn)O(\log n)O(logn)，二分遍历数组。
- 空间复杂度：O(1)O(1)O(1)，仅用常数级额外变量。
