目录
问题描述
代码解决以及思想
知识点
问题描述
代码解决以及思想
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int left = 0; // 定义左边界int right = nums.size() - 1; // 定义右边界while (left <= right) { // 当左边界小于或等于右边界时,执行循环int middle = left + (right - left) / 2; // 计算中间位置,避免整数溢出if (nums[middle] == target) { // 如果中间元素等于目标int start = middle; // 初始化起始和结束索引为中间索引int end = middle;// 向左搜索边界while (start > 0 && nums[start - 1] == target) {start--; // 向左移动起始索引,直到不再与目标相等}// 向右搜索边界while (end < (nums.size() - 1) && nums[end + 1] == target) {end++; // 向右移动结束索引,直到不再与目标相等}return {start, end}; // 返回搜索到的左右边界}else if (nums[middle] > target) {right = middle - 1; // 目标在左半部分,更新右边界}else {left = middle + 1; // 目标在右半部分,更新左边界}}return {-1, -1}; // 如果未找到目标元素,返回{-1, -1}表示未找到}
};
初始化左边界
left
为数组的起始位置(0),右边界right
为数组的结束位置(nums.size() - 1
)。进入一个循环,只要左边界
left
不大于右边界right
,就执行以下操作:a. 计算中间位置
middle
,这是为了进行二分查找,以避免整数溢出。b. 如果
nums[middle]
等于目标元素target
,则表示找到了目标元素,然后开始搜索其范围。c. 初始化
start
和end
为middle
,然后向左和向右搜索边界:
- 向左搜索边界
start
,通过不断将start
减小直到不再与目标元素相等。- 向右搜索边界
end
,通过不断将end
增加直到不再与目标元素相等。d. 返回搜索到的左右边界,它们代表了目标元素在数组中的范围。
如果在循环中找到目标元素,则会在适当的时候返回搜索到的范围。
如果未找到目标元素,循环结束后,返回
{-1, -1}
,表示未找到目标元素。
知识点
进行二分查找以找到目标元素,然后在找到目标元素后,继续向左和向右搜索以确定它的范围。对于二分查找的内容可以看看下面的链接:
82.二分查找-CSDN博客
写在最后:以上就是本篇文章的内容了,感谢你的阅读。如果感到有所收获的话可以给博主点一个赞哦。如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~