题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
输入: [1,3,5,6], 5 输出: 2
输入: [1,3,5,6], 2 输出: 1
输入: [1,3,5,6], 7 输出: 4
输入: [1,3,5,6], 0 输出: 0
分析
最直观的就是遍历，从第一个元素开始，如果target比数组第一个元素小或者相等，那么位置就是0；
如果target大于前一个元素而且小于等于后一个元素，说明后一个元素的位置就是其插入的位置。
如果，整个数组都遍历完，还没有满足上述情况的，说明数组最右一个元素都没有target大，那么target插入到数组的最后。
代码
class Solution {
public int searchInsert(int[] nums, int target) {
int i = 0;
if(target <= nums[i]){
return i;
}
for(int j = 1; j < nums.length; j++){
if(target > nums[i] && target <= nums[j]){
return j;
}
i++;
}
return nums.length;
}
}
分析这个方法，时间复杂度为O(n)，因为我们遍历的整个数组。考虑到数组有序，我们分析二分查找法。
二分查找可以将时间复杂度降低到O(logn)
过程如下图：
代码二
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (left + right)/2;
if(target == nums[mid]){
return mid;
}else if(target > nums[mid]){
left = mid +1;
}else{
right = mid -1;
}
}
return left;
}
}
