题意懒得抄了,大概是:在升序数组中给定整数target,找到第一个和最后一个target的索引,找到返回{index1, index2},否则返回{-1, -1};

时间复杂度要求:O(logn)

分析:要求对数时间,又是查找,我们不难想到二分查找。但是有一点,怎么查到第一个和最后一个呢?这困扰了我。

算法:来自leetcode caikehe

1. 使用二分变体,查找target作为index1,再找target+1, 作为index2;

2. 对index做判断,如果它未越界且它的对应值等于target则返回{index1, index2-1};否则,返回{-1, -1};

源码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //binary find
        int index1 = binarySearch(nums, target);
        int index2 = binarySearch(nums, target+1) - 1;
        if(index1 < nums.size() && nums[index1] == target)
            return {index1, index2};
        return {-1, -1};
    }
    //二分变体
    int binarySearch(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size()-1;
        while(l <= r)
        {
            int mid = l + (r-l)/2;
            if(nums[mid] < target)
                l = mid + 1;
            else
                r = mid -1;
        }
        return l;
    }
};