Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Accepted 371,213 Submissions 1,076,399      

class Solution {
public:
    int bs(vector<int> &n,int t)
    {
        int l=0,r=n.size()-1,m;
        while(l<=r)
        {
            m=(l+r)/2;
            if(n[m]<t)
                l=m+1;
            else
                r=m-1;
        }
        return l;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int idx1=bs(nums,target);
        int idx2=bs(nums,target+1)-1;
        if(idx1<nums.size()&&nums[idx1]==target)
            return {idx1,idx2};
        return {-1,-1};
    }
};

 

二分查找有三个函数 , 1 binary_search 2 lower_bound 3 upper_bound 本题用lower_bound即可解决. 这三个函数基本实现方法类似, 细微区别在于 1 需要用==来判断middle和target是否相等, 相等则返回. 2 是不判断相等,只判断 middle<target, 返回值不是middle,是left 3 同理, 只判断target<middle      

private static int lowerBound(int[] a, int low, int high, int element){
    while(low < high){
        int middle = low + (high - low)/2;
        if(element > a[middle])
            low = middle + 1;
        else 
            high = middle;
    }
    return low;
}


private static int upperBound(int[] a, int low, int high, int element){
    while(low < high){
        int middle = low + (high - low)/2;
        if(a[middle] > element)
            high = middle;
        else 
            low = middle + 1;
    }
    return low;
}