二分算法实战：查找元素首尾位置与区间查询
当解具有二段性时，二分算法是寻找答案的高效工具。核心思路是根据待查找区间的中点位置，分析答案落在哪一侧，随后舍弃一半区间，在剩余部分继续查找。
时间复杂度：O(logN)
STL 中的二分查找
- lower_bound：返回大于等于 x 的最小元素迭代器，时间复杂度 O(log N)。
- upper_bound：返回大于 x 的最小元素迭代器，时间复杂度 O(log N)。
一、在排序数组中查找元素的第一个和最后一个位置
1. 题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值，返回 [-1, -1]。
2. 算法原理
我们需要分别找到目标值的左边界和右边界。
左右端点求法：
- 定义两个指针指向数组的头和尾。
- 进行二分区间划分。
- 判断获取的端点值是否合法（即是否等于 target）。
二分容易死循环的环节：
- 区间缩小头尾指针的相遇条件。
- 中值的求法（注意向上取整或向下取整对边界的影响）。
3. 代码实现
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};
}
};
