二分查找算法 （典型算法思想）—— OJ例题算法解析思路
目录
一、704. 二分查找 - 力扣（LeetCode）
运行代码：
1. 核心思想
2. 代码思路
初始化
循环条件
计算中间位置
比较中间值与目标值
未找到目标值
3. 关键点
4. 示例
二、34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
运行代码：
1. 核心思想
2. 代码思路
边界情况处理
第一次二分查找：查找起始位置（左端点）
第二次二分查找：查找结束位置（右端点）
3. 关键点
4. 示例
5. 代码总结
超级重点：
1. 第一次二分查找：查找起始位置（左端点）
目标
实现逻辑
为什么这样设计？
示例
2. 第二次二分查找：查找结束位置（右端点）
目标
实现逻辑
为什么这样设计？
示例
3. 总结两次二分查找的差异
4. 为什么不能统一写法？
5. 示例分析
6. 结论
三、35. 搜索插入位置 - 力扣（LeetCode）
运行代码：
1. 核心思想
2. 代码思路
初始化
二分查找
循环结束后的处理
3. 关键点
4. 示例
示例 1：
示例 2：
示例 3：
四、69. x 的平方根 - 力扣（LeetCode）
方法一：暴力查找
运行代码：
方法二：二分查找算法
运行代码：
1. 边界情况处理
2. 二分查找
3. 循环查找
4. 终止条件
5. 返回结果
总结
五、852. 山脉数组的峰顶索引 - 力扣（LeetCode）
运行代码：
1. 初始化指针
2. 二分查找循环
3. 返回结果
关键点解析
示例验证
复杂度
六、162. 寻找峰值 - 力扣（LeetCode）
运行代码：
1. 初始化指针
2. 二分查找循环
3. 返回结果
关键点解析
示例验证
复杂度
七、153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
运行代码：
1. 初始化指针
2. 二分查找循环
3. 返回结果
关键点解析
示例验证
复杂度
八、LCR 173. 点名 - 力扣（LeetCode）
运行代码：
1. 初始化指针
2. 二分查找循环
3. 返回结果
关键点解析
示例验证
复杂度
一、704. 二分查找 - 力扣（LeetCode）
运行代码：
class Solution {
public:int search(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 if(nums[mid]>target){right=mid-1;}else{return mid;}}return -1;}
};1. 核心思想
二分查找的核心思想是通过分治策略，每次将搜索区间缩小一半，从而快速定位目标值。它的时间复杂度是 O(log n)，效率非常高。
2. 代码思路
初始化
-
left和right分别表示当前搜索区间的左右边界。-
left = 0：初始左边界，指向数组的第一个元素。 -
right = nums.size() - 1：初始右边界，指向数组的最后一个元素。
-
循环条件
-
while (left <= right)：-
当
left <= right时，说明当前搜索区间仍然有效，可以继续查找。 -
如果
left > right，说明搜索区间已经无效，目标值不存在，退出循环并返回-1。
-
计算中间位置
-
int mid = left + (right - left) / 2：-
计算当前区间的中间位置
mid。 -
使用
left + (right - left) / 2而不是(left + right) / 2，是为了避免left + right可能导致的整数溢出问题。
-
比较中间值与目标值
-
if (nums[mid] < target)：-
如果中间值小于目标值，说明目标值在右半部分，更新左边界
left = mid + 1。
-
-
else if (nums[mid] > target)：-
如果中间值大于目标值，说明目标值在左半部分，更新右边界
right = mid - 1。
-
-
else：-
如果中间值等于目标值，说明找到了目标值，直接返回
mid（目标值的索引）。
-
未找到目标值
-
如果循环结束仍未找到目标值，返回
-1，表示目标值不存在于数组中。
3. 关键点
-
有序数组：
-
二分查找的前提是数组必须是有序的（升序或降序）。如果数组无序，需要先排序。
-
-
区间更新：
-
每次比较后，区间会被缩小一半：
-
如果
nums[mid] < target，目标值在右半部分，更新left = mid + 1。 -
如果
nums[mid] > target，目标值在左半部分，更新right = mid - 1。
-
-
-
循环条件：
-
left <= right确保在left == right时仍然检查最后一个可能的元素。
-
-
返回值：
-
找到目标值时返回其索引。
-
未找到时返回
-1。
-
4. 示例
假设数组为 [1, 2, 3, 4, 5]，目标值为 4：
-
初始区间：
left = 0，right = 4。 -
第一次循环：
-
mid = 2，nums[mid] = 3。 -
3 < 4，更新left = 3。
-
-
第二次循环：
-
mid = 3，nums[mid] = 4。 -
找到目标值，返回
3。
-
二、34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
运行代码：
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 处理边界情况if (nums.size() == 0)return {-1, -1};int begin = 0;// 1. ⼆分左端点int left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}// 判断是否有结果if (nums[left] != target)return {-1, -1};elsebegin = left; // 标记⼀下左端点// 2. ⼆分右端点left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (nums[mid] <= target)left = mid;elseright = mid - 1;}return {begin, right};}
};1. 核心思想
-
使用两次二分查找：
-
第一次二分查找目标值的起始位置（左端点）。
-
第二次二分查找目标值的结束位置（右端点）。
-
-
通过两次二分查找，可以高效地找到目标值的区间范围。
2. 代码思路
边界情况处理
-
如果数组为空（
nums.size() == 0），直接返回{-1, -1}，因为目标值不可能存在于空数组中。
第一次二分查找：查找起始位置（左端点）
-
初始化：
-
left = 0，right = nums.size() - 1。
-
-
循环条件：
-
while (left < right)：当left == right时，退出循环。
-
-
计算中间位置：
-
int mid = left + (right - left) / 2。
-
-
比较中间值与目标值：
-
如果
nums[mid] < target，说明目标值在右半部分，更新left = mid + 1。 -
否则（
nums[mid] >= target），说明目标值在左半部分或当前位置就是起始位置，更新right = mid。
-
-
判断是否找到目标值：
-
如果
nums[left] != target，说明目标值不存在，返回{-1, -1}。 -
否则，记录起始位置
begin = left。
-
第二次二分查找：查找结束位置（右端点）
-
初始化：
-
left = 0，right = nums.size() - 1。
-
-
循环条件：
-
while (left < right)：当left == right时，退出循环。
-
-
计算中间位置：
-
int mid = left + (right - left + 1) / 2：-
这里
+1是为了避免死循环（当left和right相邻时，mid会偏向右侧）。
-
-
-
比较中间值与目标值：
-
如果
nums[mid] <= target，说明目标值在右半部分或当前位置就是结束位置，更新left = mid。 -
否则（
nums[mid] > target），说明目标值在左半部分，更新right = mid - 1。
-
-
返回结果：
-
返回
{begin, right}，其中begin是起始位置，right是结束位置。
-
3. 关键点
-
两次二分查找：
-
第一次查找目标值的起始位置。
-
第二次查找目标值的结束位置。
-
-
查找起始位置：
-
当
nums[mid] >= target时，更新right = mid，因为目标值可能在左半部分或当前位置就是起始位置。
-
-
查找结束位置：
-
当
nums[mid] <= target时，更新left = mid，因为目标值可能在右半部分或当前位置就是结束位置。 -
计算
mid时+1，是为了避免死循环。
-
-
边界条件：
-
如果数组为空，直接返回
{-1, -1}。 -
如果第一次二分查找未找到目标值，直接返回
{-1, -1}。
-
4. 示例
假设数组为 [5, 7, 7, 8, 8, 10]，目标值为 8：
-
第一次二分查找（起始位置）：
-
初始区间：
left = 0，right = 5。 -
第一次循环：
-
mid = 2，nums[mid] = 7。 -
7 < 8，更新left = 3。
-
-
第二次循环：
-
mid = 4，nums[mid] = 8。 -
8 >= 8，更新right = 4。
-
-
第三次循环：
-
left == right，退出循环。
-
-
检查
nums[left] == 8，记录起始位置begin = 3。
-
-
第二次二分查找（结束位置）：
-
初始区间：
left = 0，right = 5。 -
第一次循环：
-
mid = 3，nums[mid] = 8。 -
8 <= 8，更新left = 3。
-
-
第二次循环：
-
mid = 4，nums[mid] = 8。 -
8 <= 8，更新left = 4。
-
-
第三次循环：
-
mid = 5，nums[mid] = 10。 -
10 > 8，更新right = 4。
-
-
退出循环，返回
{3, 4}。
-
5. 代码总结
这是一种高效且经典的解决有序数组中查找目标值区间的方法，时间复杂度为 O(log n)。