# 2.搜索插入的位置（easy）

TIP

更好的阅读体验应该是：

审题-思考
答题
整理-归纳

# 一、题目

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

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

示例 1:

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

示例 2:

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

# 二、题解一（二分法）

在一个排序的数组查找，我们可以使用二分法

我们的目的是：查找一个下标index，我们要找的target <= nums[mid]的第一个值。

如果找不到，就返回数组的长度

时间复杂度：O(log(n))
空间复杂度：O(1)

分析模版

目标存在对应target === nums[mid]
目标不存在对应target < nums[mid]，即找到第一个比目标值大的，目标值将会加入此位置

Javasciprt 代码

var searchInsert = function(nums, target) {
  const len = nums.length;
  let left = 0; //左边界
  let right = len - 1; // 右边界
  let ans = len; // 返回值，注意如果目标不在数组中，返回数组的长度
  while (left <= right) {
    mid = ((right - left) >> 1) + left;
    if (target <= nums[mid]) { // 合并条件
      // 证明左边界在数组内部
      ans = mid; // 更新返回值
      right = mid - 1; // 既然已经保存了次目标值，就可以移除它的
    } else {
      left = mid + 1;
    }
  }
  return ans;
};

# 三、题解二（暴力法）

提到暴力法，就是频繁的使用遍历，且没有所谓的“套路”，从上倒下透漏出的都是实在！

时间复杂度：O(n) 空间复杂度：O(1)

思路

找到第一比 target 大的元素，它的下标，就是要答案。

实现

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

# 四、写在最后

这是二分法解题的第二篇文章，与基础模版相比，它只是修改 target === nums[mid]这一个判定条件。

如果对你有所帮助不妨给本项目的github 点个 star (opens new window)，这是对我最大的鼓励~

关于我

花名：余光
WX：j565017805
沉迷JS，水平有限，虚心学习中

其他沉淀

如果您看到了最后，不妨点个star吧，这就是对我最大的鼓励！