力扣：搜索插入位置
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] <= 104nums?為?無重復(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
