34. 在排序数组中查找元素的第一个和最后一个位置-526互联

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

 

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

二分法

二分查找为什么总是写错？

蓝色标记左边区域，浅蓝色边框代表元素尚未着色，蓝色边框代表元素已经着色；红色标记右边区域，浅红色边框代表元素尚未着色，红色边框代表元素已经着色；

二分查找起始状态：

Screen Shot 2021-08-30 at 3.35.42 PM.png

代码


class Solution {
public:
    int searchleft(vector<int>& nums, int target) {
        int l = -1;
        int r = nums.size();
        while(l + 1 != r){
            int mid = l + (r - l)/2;
            if(nums[mid] >= target){
                r = mid;
            }
            else{
                l = mid;
            }
        }
        return r;
    }
    int searchright(vector<int>& nums, int target) {
        int l = -1;
        int r = nums.size();
        while(l + 1 != r){
            int mid = l + (r - l)/2;
            if(nums[mid] <= target){
                l = mid;
            }
            else{
                r = mid;
            }
        }
        return l;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftdex = searchleft(nums,target);
        int rightdex = searchright(nums,target);
        if(leftdex <= rightdex && rightdex < nums.size() && nums[leftdex] == target && nums[rightdex] == target){
            return { leftdex , rightdex};
        }
        else{
            return { -1 , -1};
        }
    }
};

库函数


class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) {
            return {-1, -1};
        }
        int leftIdx = lower_bound(nums.begin(), nums.end(), target)-nums.begin();
        int rightIdx = upper_bound(nums.begin(), nums.end(), target)-1-nums.begin();
        if(leftIdx<=rightIdx && rightIdx<nums.size() && nums[leftIdx]==target && nums[rightIdx]==target) {
            return {leftIdx, rightIdx};
        }
        return {-1, -1};
    }
};