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