【刷题第六天】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

二、思路分析：

题目与以往接触略有区别，以往题目大多只有搜索索引情况，但本题目加入了如果搜索不到，则添加到对应位置。

虽然增加了一个额外条件，但第一想法还是二分查找，只不过在于如何修改条件，能满足额外情况。

二分查找变体一般都在与修改判断条件。我们考虑插入位置 pos，应该满足下列条件:

nums[pos−1]< target <=nums[pos]

nums[pos-1]< target <=nums[pos]

nums[pos−1]< target <=nums[pos]

nums 为排列数组，如果存在这个值，最终的结果也是返回 pos 位置，如果不存在则在 pos 位置插入值，因此本题目可以转化为 寻找第一个大于等于 target 的下标

通过上面的分析，我们已经成功的把该问题转化为了二分查找问题，下面开始套模板: 即通过使用二分法逼近查找第一个大于等于 target 的下标。

如果 target 大于数组中的所有元素，就会插入在第 n 个位置。因此下面代码中 res 初始值赋值为 n，可以避免这种情况的特殊判断。

三、AC 代码：

var searchInsert = function (nums, target) {  const n = nums.length;  let start = 0;  let end = n - 1;  // 处理临界情况  let res = n;
  while (start <= end) {    // 避免越界    let mid = (end - start) / 1 + start;    if (target <= nums[mid]) {      res = mid;      end = mid - 1;    } else {      start = mid + 1;    }  }  return res;};复制代码

四、总结：

好久没有做二分查找的问题了，第一瞬间竟然没有转化好，转化成功后，可以很清楚的看到这就是个二分问题。加油!!!