LeetCode 热题 100_在排序数组中查找元素的第一个和最后一个位置（65_34）
- 题目描述：
- 输入输出样例：
- 题解：
- 解题思路：
- 思路一（一次二分查找+挨个搜索）：
- 思路二（两次二分查找）：
- 代码实现
- 代码实现（思路一（二分查找+挨个搜索））：
- 代码实现（思路二（两次二分查找））：
- 以思路二为例进行调试
题目描述：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
输入输出样例：
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
题解：
解题思路：
思路一（一次二分查找+挨个搜索）：
1、通过二分查找找到第一个等于target的元素，若没查找到等于target的元素则返回[-1,-1]。若查找到target的元素，则从此位置开始分别向左向右挨个判断元素值是否为target，直至元素值不等于target为止，此时更新最左侧和最右侧的下标。
2、复杂度分析：
① 时间复杂度：O(n)，n代表数组中元素的个数，最坏的情况：数组中的元素都为target。
② 空间复杂度：O(1)。
思路二（两次二分查找）：
1、可以通过二分查找先查找到等于target值元素的最左侧下标，再采用二分查找找到等于target值元素的最右侧的下标。
① 当元素值等于target值的时候，再在左侧区间查找是否有等于target值的元素，有则更新等于target的左侧下标，直至左侧子区间不存在等于target值的元素。
② 当元素值等于target值的时候，再在右侧区间查找是否有等于target值的元素，有则更新等于target的右侧下标，直至右侧子区间不存在等于target值的元素。
2、复杂度分析
① 时间复杂度：O(logn)，n代表数组中元素的个数。
② 空间复杂度：O(1)。
代码实现
代码实现（思路一（二分查找+挨个搜索））：
class Solution1 {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 初始化返回的结果为 {-1, -1}，表示未找到目标值
vector<int> ans = {-1, -1};
// 如果数组为空，直接返回 {-1, -1}
if (nums.empty())
{
return ans;
}
// 初始化二分查找的左右边界
int left = 0, right = nums.size() - 1;
int mid;
// 使用二分查找寻找目标值的某个位置
while (left <= right)
{
// 计算中间位置
mid = left + (right - left) / 2;
// 如果中间值大于目标值，缩小右边界
if (nums[mid] > target)
{
right = mid - 1;
}
// 如果中间值小于目标值，缩小左边界
else if (nums[mid] < target) {
left = mid + 1;
}
// 如果找到了目标值，记录当前中间值位置，并跳出循环
else {
ans[0] = mid; // 目标值的起始位置
ans[1] = mid; // 目标值的结束位置
break; // 找到目标值，跳出循环
}
}
// 如果找到了目标值（即ans[0]不为-1）
if (ans[0] != -1)
{
// 在找到的位置周围扩展，查找目标值的左边界和右边界
left = ans[0];
right = ans[1];
// 从左边界开始，向左扩展，直到不等于目标值为止
while (left >= 0 && nums[left] == target){
left--;
}
// 更新目标值的左边界
ans[0] = left + 1;
// 从右边界开始，向右扩展，直到不等于目标值为止
while (right < nums.size() && nums[right] == target){
right++;
}
// 更新目标值的右边界
ans[1] = right - 1;
}
// 返回目标值的范围
return ans;
}
};
代码实现（思路二（两次二分查找））：
class Solution2 {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans = {-1, -1};
if (nums.empty()) {
return ans;
}
// 寻找左边界
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 {
// 找到目标，继续向左移动 right 确保是最左边的位置
right = mid - 1;
}
}
//这里不能使用left<=right来判断是否找到target，因我们再继续查找其他的target时会令最终的left>right
// 如果 left 超出了数组范围，或者 nums[left] 不是 target，说明 target 不存在
if (left >= nums.size() || nums[left] != target) {
return ans;
}
ans[0] = left;
// 寻找右边界
right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
// 找到目标，继续向右移动 left 确保是最右边的位置
left = mid + 1;
}
}
ans[1] = right;
return ans;
}
};
以思路二为例进行调试
#include<iostream>
#include <vector>
using namespace std;
class Solution2 {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans = {-1, -1};
if (nums.empty()) {
return ans;
}
// 寻找左边界
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 {
// 找到目标，继续向左移动 right 确保是最左边的位置
right = mid - 1;
}
}
//这里不能使用left<=right来判断是否找到target，因我们再继续查找其他的target时会令最终的left>right
// 如果 left 超出了数组范围，或者 nums[left] 不是 target，说明 target 不存在
if (left >= nums.size() || nums[left] != target) {
return ans;
}
ans[0] = left;
// 寻找右边界
right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
// 找到目标，继续向右移动 left 确保是最右边的位置
left = mid + 1;
}
}
ans[1] = right;
return ans;
}
};
int main(int argc, char const *argv[])
{
vector<int> nums={5,7,7,8,8,10};
int target= 8;
Solution2 s2;
vector<int>ans= s2.searchRange(nums,target);
cout<<ans[0]<<" "<<ans[1];
return 0;
}
LeetCode 热题 100_在排序数组中查找元素的第一个和最后一个位置（65_34)原题链接
欢迎大家和我沟通交流(✿◠‿◠)
