給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標(biāo)值 target价说。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置能颁。
你的算法時間復(fù)雜度必須是?O(log n) 級別。
如果數(shù)組中不存在目標(biāo)值旁涤，返回?[-1, -1]。
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
示例?2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]
class?Solution?{
public:
????int?left(vector<int>&?nums,int?target)
????{
????????int?l?=?0;
????????int?r?=?nums.size()-1;
????????while(l?<=?r)
????????{
????????????int?mid?=?(l?+?r)/2;
????????????if(target?==?nums[mid])
????????????{
????????????????if(mid?==?0?||?target?>?nums[mid?-?1])
????????????????????return?mid;
????????????????r?=?mid?-?1;
????????????}
????????????else?if(nums[mid]?<?target)
?????????????????l?=?mid?+?1;
????????????else?if(nums[mid]?>?target)
????????????????r?=?mid?-?1;
????????}
????????return?-1;
????}
????int?right(vector<int>&?nums,int?target)
????{
????????int?l?=?0;
????????int?r?=?nums.size()-1;
????????while(l?<=?r)
????????{
????????????int?mid?=?(l?+?r)/2;
????????????if(target?==?nums[mid])
????????????{
????????????????if(mid?==?nums.size()?-?1?||?target?<?nums[mid?+?1])
????????????????????return?mid;
????????????????l?=?mid?+?1;
????????????}
????????????else?if(nums[mid]?<?target)
?????????????????l?=?mid?+?1;
????????????else?if(nums[mid]?>?target)
????????????????r?=?mid?-?1;
????????}
????????return?-1;
????}
????vector<int>?searchRange(vector<int>&?nums,?int?target)?{
????????int?l?=?left(nums,target);
????????int?r?=?right(nums,target);
????????vector<int>?vec;
????????vec.push_back(l);
????????vec.push_back(r);
????????return?vec;
????}
};
