1. 题目

Search for a Range

2. 算法

• stl:O(lgn)

使用lower_bound和upper_bound

• 直接二分查找

3. 代码

3.1 stl

class Solution{

public:

vector<int> searchRange(vector<int>& nums, int target){

     vector<int>::iterator lower=lower_bound(nums.begin(),nums.end(),target);

//lower_bound返回第一个大于等于value值得位置

     vector<int>::iterator upper=upper_bound(nums.begin(),nums.end(),target);

//upper是第一个大于value的位置

    vector<int> ret;

    ret.push_back(-1);

    ret.push_back(-1);

    vector<int> resultNo;

    resultNo.push_back(lower-nums.begin());

    resultNo.push_back(upper-nums.begin()-1);

    if(*lower!=target)

        return ret;

    else

        return resultNo;

    }

};

3.2 直接二分查找

class Solution{

public:    vector<int> searchRange(vector<int>& nums, int target){

        vector<int> ret;

        ret.push_back(-1);

        ret.push_back(-1);

        int left=0,right=nums.size()-1,mid;

        while(left<=right){

            if(nums[left]==target && nums[right]==target){

                ret[0]=left;

                ret[1]=right;

                break;

            }

            mid=left+(right-left)/2;

            if(nums[mid]<target)

                left=mid+1;

            else if(nums[mid]>target)

                right=mid-1;

            else{

                if(nums[right]==target)

                    ++left;

                else

                    --right;

            }

        }

     return ret;

  }

};