35. 搜索插入位置

難度簡單1914收藏分享切換為英文接收動態(tài)反饋

給定一個排序數(shù)組和一個目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置。

請必須使用時間復(fù)雜度為?O(log n)?的算法。

?

示例 1:

輸入: nums = [1,3,5,6], target = 5輸出: 2

示例?2:

輸入: nums = [1,3,5,6], target = 2輸出: 1

示例 3:

輸入: nums = [1,3,5,6], target = 7輸出: 4

?

提示:

• 1 <= nums.length <= 104

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

• nums?為?無重復(fù)元素?的?升序?排列數(shù)組

• -104?<= target <= 104

第一種錯法：

class?Solution?{

public:

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

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

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

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

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

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

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

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

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

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

????????????????return?mid;

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

????????}

????????return?mid+1;//這里錯了

????}

};

不是返回mid+1因?yàn)閙id沒辦法小于0（-1）而添加的位置可以在0這里思考錯了

第一種對法：

class?Solution?{

public:

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

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

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

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

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

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

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

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

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

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

????????????????return?mid;

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

????????}

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

????????????return mid;

????????}else{

????? ? return mid+1;?

????????}

????}

};

在最后那里分辨了一下nums與target的大小

第二種對法：

class?Solution?{

public:

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

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

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

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

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

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

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

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

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

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

????????????????return?mid;

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

????????}

????????return?right+1;

????}

};

right在最后可以變成-1