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

这是一个有序的数组，最简单的办法是从头到尾遍历，找到合适的位置，时间复杂度O（n）

var searchInsert = function(nums, target) {
    var num = nums.length;
    if (num===0)
        return 0;
    for (var i = 0;i < num;i++) {
        if (nums[i]>=target)
            return i;
    }
    return num;
};

还有一种就是使用二分法进行搜索：

var searchInsert = function(nums, target) {
    if (target<=nums[0])
        return 0;
    var num = nums.length;
    var left = 0;
    var right = num-1;
    while (left<=right) {
        var mid = left + parseInt((right-left)/2);
        if (target===nums[mid])
            return mid;
        if (mid === nums[num-1]) 
            return num;
        if (target>nums[mid]&&target<nums[mid+1])
            return mid+1;
        if (target>nums[mid])
            left = mid + 1;
        else 
            right = mid;
    }
    return num;
};