35. 搜索插入位置

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

输入: [1,3,5,6], 2
输出: 1

注意

• 如果数组中已经存在相同的数字，插入位置是当前数字的前一位

  输入: [1,3,5,6], 5
  输出: 2

暴力解法

var searchInsert = function (nums, target) {
    var i = 0,
        len = nums.length;
    // 处理边界
    if (nums[len - 1] < target) return len;
    if (nums[len - 1] === target) return len - 1;
    for (; i < len - 1; i++) {
        if (nums[i] === target) return i;
        if (nums[i] < target && nums[i + 1] > target) {
            return i + 1;
        }
    }
};

二分法

此题很容易想到用二分法解决，如果在一个给定范围的数组中查询某一项，大概率可以使用二分法。

思路

• 定义左下标left,和右下标right
• 计算mid=Math.floor(left+right),向下取整保证下表位整数
• 根据nums[mid]值来判断，如果nums[mid]===target 返回mid，如果nums[mid]<target说明mid左侧值全都比mid小，下次比较时只需要关心mid右侧值，所以left变为mid的下一位，left=mid+1. 同理，nums[mid]>target 只需要关心mid左侧值，right=mid-1
• 最后如果没有和mid相等的情况是返回left即位插入的位置.

为什么可以使用left作为返回结果？
因为向下取整所以在相邻位置时left===mid

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

复杂度分析

• 时间复杂度：

• 空间复杂度：

打赏