# 35.Search Insert Position

## August 19, 2016

35.Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0


/*solution1*/
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.empty()||target<nums[0])
return 0;
int low=0,size=nums.size(),high=size-1,mid=0,i=0;
while(low<=high){
mid=low+(high-low)/2;
if(nums[mid]==target)
return mid;
if(nums[mid]>target)
high=mid-1;
else
low=mid+1;
}
// if not found,let varible i go back to find an exact position
for(i=size;i>=0&&nums[i-1]>target;i--);
return i;
}
};


/*solution2*/
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
if(nums.empty()||target<nums[0])
return 0;
int low=0,size=nums.size(),high=size-1,mid=0,i=0;
while(low<=high){
mid=low+(high-low)/2;
if(nums[mid]==target)
return mid;
if(nums[mid]>target)
high=mid-1;
else
low=mid+1;
}
return low;
}
};



### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017