LeetCode 热题 100_在排序数组中查找元素的第一个和最后一个位置（65_34_中等_C++）(二分查找)(一次二分查找+挨个搜索；两次二分查找)

题目描述：

给你一个按照非递减顺序排列的整数数组 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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums 是一个非递减数组
-10⁹ <= target <= 10⁹

题解：

解题思路：

思路一（一次二分查找+挨个搜索）：

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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)