Search for a Range

class Solution {

public:

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

vector<int> ret;

int l=binarySearch(nums,target,0,nums.size()-1,true);

int r=binarySearch(nums,target,0,nums.size()-1,false);

ret.push_back(l);

ret.push_back(r);

return ret;

}

int binarySearch(vector<int>& nums, int target,int l,int h, bool left){

if(l>h) return -1;

int m=(h+l)/2;

if(nums[m]==target){

int pos=left ? binarySearch(nums,target,l,m-1,left) : binarySearch(nums,target,m+1,h,left);

return pos==-1 ? m : pos;

}else if(nums[m]>target){

binarySearch(nums,target,l,m-1,left);

}else{

binarySearch(nums,target,m+1,h,left);

}

}

};

Last updated

Was this helpful?