二分算法简介
当问题的解具备二段性时，通常可以使用二分算法快速定位答案。核心思路是根据待查找区间的中点位置，分析目标值会出现在哪一侧，随后舍弃一半区间，在剩余部分继续二分。
时间复杂度通常为 O(logN)。
C++ STL 中提供了便捷的二分函数：
lower_bound：返回大于等于 x 的最小元素的迭代器。upper_bound：返回大于 x 的最小元素的迭代器。 两者时间复杂度均为 O(log N)。
实现时需注意 mid 的计算方式及循环终止条件，避免死循环。
题目一：在排序数组中查找元素的第一个和最后一个位置
问题描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值，返回 [-1, -1]。
思路解析
我们需要分别找到目标值的左边界和右边界。
- 找左边界：使用二分查找，当
nums[mid] >= target时，收缩右指针；否则收缩左指针。最终检查nums[left]是否等于 target。 - 找右边界：类似地，当
nums[mid] <= target时，收缩左指针；否则收缩右指针。注意 mid 计算需向上取整以防死循环。 - 合法性判断：搜索结束后必须验证端点值是否真的等于 target，防止找不到目标值的情况。
代码实现
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) / 2;
if (nums[mid] >= target) right = mid;
else left = mid + 1;
}
(nums[left] != target) {, };
retLeft = left;
left = ; right = nums.() - ;
(left < right) {
mid = (left + right + ) / ;
(nums[mid] <= target) left = mid;
right = mid - ;
}
{retLeft, right};
}
};
