題目：

34. 在排序數(shù)組中查找元素的第一個和最后一個位置

難度中等2187收藏分享切換為英文接收動態(tài)反饋

給你一個按照非遞減順序排列的整數(shù)數(shù)組?nums，和一個目標值?target。請你找出給定目標值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標值?target，返回?[-1, -1]。

你必須設(shè)計并實現(xiàn)時間復雜度為?O(log n)?的算法解決此問題。

?

示例 1：

輸入：nums = [5,7,7,8,8,10], target = 8輸出：[3,4]

示例?2：

輸入：nums = [5,7,7,8,8,10], target = 6輸出：[-1,-1]

示例 3：

輸入：nums = [], target = 0輸出：[-1,-1]

?

提示：

• 0 <= nums.length <= 105

• -109?<= nums[i]?<= 109

• nums?是一個非遞減數(shù)組

• -109?<= target?<= 109

第一種錯法：

class?Solution?{

public:

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

????????if(!nums.size())return?{-1,-1};

???????int?first,last;

????????first?=?searchFirst(nums,target);

????????last?=?searchLast(nums,target);

????????if(first==-1)return?{-1,-1};

????????else?return?{first,last};

????}

?????int?searchFirst(vector<int>&?nums,int?target){

????????????int?right,left,mid;

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

????????????while(right>left){

????????????????mid?=?(right?+?left)>>1;

????????????????if(nums[mid]>target){

????????????????????right?=?mid?-?1;

????????????????}else?if(nums[mid]<target){

????????????????????left?=?mid?+?1;

????????????????}else{

????????????????????right?=?mid;

????????????????}

????????????}

????????????if(nums[left]==target)return?left;

????????????else?return?-1;

????????}

????????int?searchLast(vector<int>&?nums,int?target){

????????????int?right,left,mid;

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

????????????while(right>left){

????????????????mid?=?(right?+?left?)>>1;//這里錯了

????????????????if(nums[mid]>target){

????????????????????right?=?mid?-?1;

????????????????}else?if(nums[mid]<target){

????????????????????left?=?mid?+?1;

????????????????}else{

????????????????????left?=?mid;

????????????????}

????????????}

????????????return?left;

????????}

};

因為這里searchLast是為了找這段連續(xù)數(shù)字的末尾的位置，應(yīng)該要取右邊界，就是向上取整，所以不能mid?=?(right?+?left?)>>1，而是要mid?=?(right?+?left +1)>>1

，不然會陷入無限循環(huán)；

第一種對法：

class?Solution?{

public:

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

????????if(!nums.size())return?{-1,-1};

???????int?first,last;

????????first?=?searchFirst(nums,target);

????????last?=?searchLast(nums,target);

????????if(first==-1)return?{-1,-1};

????????else?return?{first,last};

????}

?????int?searchFirst(vector<int>&?nums,int?target){

????????????int?right,left,mid;

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

????????????while(right>left){

????????????????mid?=?(right?+?left)>>1;

????????????????if(nums[mid]>target){

????????????????????right?=?mid?-?1;

????????????????}else?if(nums[mid]<target){

????????????????????left?=?mid?+?1;

????????????????}else{

????????????????????right?=?mid;

????????????????}

????????????}

????????????if(nums[left]==target)return?left;

????????????else?return?-1;

????????}

????????int?searchLast(vector<int>&?nums,int?target){

????????????int?right,left,mid;

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

????????????while(right>left){

????????????????mid?=?(right?+?left + 1)>>1;

????????????????if(nums[mid]>target){

????????????????????right?=?mid?-?1;

????????????????}else?if(nums[mid]<target){

????????????????????left?=?mid?+?1;

????????????????}else{

????????????????????left?=?mid;

????????????????}

????????????}

????????????return?left;

????????}

};

searchFirst是向下取整，取左邊界，searchLast是向上取整，取右邊界