14 - 搜索插入位置

题目

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

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

示例 1:

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

示例 2:

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

示例 3:

输入: [1,3,5,6], 7 输出: 4

示例 4:

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

解答

感觉和two sum差不多，可以用哈希表和两分法

暴力解法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
  if (nums[0] > target) {
    return 0;
  }
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] >= target) {
      return i;
    }
  }
  return nums.length;
};

Runtime: 52 ms, faster than 85.47% of JavaScript online submissions for Search Insert Position.

Memory Usage: 34.3 MB, less than 41.45% of JavaScript online submissions for Search Insert Position.

双指针

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
  if (nums[0] > target) {
    return 0;
  } else if (nums[nums.length - 1] < target) {
    return nums.length;
  }
  let start = 0;
  end = nums.length - 1;
  while (start <= end) {
    let mid = Math.round((start + end) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return start;
};

Runtime: 76 ms, faster than 5.48% of JavaScript online submissions forSearch Insert Position.

Memory Usage: 33.9 MB, less than 59.44% of JavaScript online submissions for Search Insert Position.

这运行时间简直惊呆了。。。

二分法

作者：liweiwei1419

链接：https://leetcode-cn.com/problems/two-sum/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/

这个liweiwei大佬可太厉害了，我刷题就知道这一题一地的解法，这个大佬还能抽象出模版，可以说是非常佩服了。

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

Runtime: 64 ms, faster than 22.58% of JavaScript online submissions for Search Insert Position.

Memory Usage: 33.7 MB, less than 98.01% of JavaScript online submissions for Search Insert Position.

基于这篇文章对这个二分法的优化：

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

Runtime: 52 ms, faster than 83.92% of JavaScript online submissions for Search Insert Position.

Memory Usage: 33.9 MB, less than 67.81% of JavaScript online submissions for Search Insert Position.

OK，那么究竟优化了哪些地方呢？

• 前7行增加了边界判断

• while的判断条件变成了小于号

之前的等号，left和right是不一样的值，那么还需要费神试出来究竟用哪个。

这里改成小于号，跳出while后，left和right都是一样的，可以再做判断等操作。

• 11行用了一个很装逼的无符号右移

结果相当于Math.floor((left + right) / 2)。而且left和right必须是正数。

那为什么要这么写呢？

原先的(left + right) / 2，如果left和right都很大的情况下，加和可能超过最大安全数，导致结果不精确。

当然可以改成left + (right - left) / 2，不过如果right很大，而left很小，也会溢出。

用>>>，不怕溢出，简单快捷，就是可读性差了点。

• if的判断条件变成了两个

原先每次都要判断一下，万一nums[mid]就是结果了呢？

其实nums[mid]能命中结果的情况很罕见，每次循环都校验一下有没有命中，就好像每次出门买张彩票，不值得。

等二分结束出结果，再拿着结果做校验，是一个整体更加高效的行为。

关于死循环

我理解死循环的触发条件是这样：

...
    let mid = (left + right) >>> 1;
        if (target > nums[mid]) {
      left = mid + 1;
    } else {
      right = mid;
    }
...

比如算mid除以2得到2.5，那么可以取上界变3，如Math.round()；也可以取下界变成2，如Math.floor()或>>>。

在if循环中，如果nums[mid]小于了target，那么结论不可能是这个mid了。因此下一轮的left可以跳过这个mid，变成mid + 1。

if对应的else，是nums[mid]大于等于了target，因此right对应的nums[right]有可能是target，就用right = mid保留。

因此，如果mid的计算取上边界，mid就可能等于right。这样就会进入else的死循环，right始终等于mid。

为了避免这个问题，只要mid的边界选取和if的判断条件一致就行了。mid取下边界，if判断小于target。

强烈建议看原文，我这个是非常简略了。