35.搜索插入位置

题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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

示例4：
输入：nums = [1,3,5,6], target = 0
输出：0

示例5：
输入：nums = [1], target = 0
输出：0

提示：

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 为无重复元素的升序排列数组
• -10^4 <= target <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position

解法一：

代码：

var searchInsert = function(nums, target) {
    let i,len = nums.length;
    if(nums.indexOf(target)!=-1)
        return nums.indexOf(target);
    else{
        for(i=0;i<len;i++){
            if(nums[i]>target)
                return i;
        }
        return i;
    }
};

执行结果：

image.png

二分法：

• ~~符号的作用是去掉小数部分！！！

代码：

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

执行结果：

image.png