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

答案

对撞指针

类似快速排序

时间复杂度为:logn

思路:

1. 声明对撞指针 left/right

2. 声明中位数 mid

3. 根据二分法比较 target，找到对应下标 mid

   • while 循环条件： while (left <= right) {}
   • nums[mid]比较target
   • 找到对应下标return mid
   • 未找到left = mid +1 / right = mid -1

4. 未找到返回下标 left

var searchInsert = function(nums, target) {
    let left = 0;                //左位：下标
    let right = nums.length - 1; //右位：下标
    let mid = 0;                //中位：下标
    while(left<=right){
        //或：mid = (low + high) >> 1  表示：该数二进制向右移一位 如：1000 >> 1 = 100 = 4(10进制)，小数点直接被抹去。
        mid = parseInt((left + right) / 2);
        if(nums[mid]==target){
            return mid;
        }else if(nums[mid]>target){
            right = mid - 1;
        }else if(nums[mid]<target){
            left = mid + 1;
        }
    }
    return left;
};

var nums = [1,3,5,6], target = 3
console.log(searchInsert(nums,target))

暴力（时间复杂度为 n）

var searchInsert = function(nums, target) {
  let index
  let sortIndex
  for(let i=0;i<nums.length;i++){
    const element = nums[i]

    if(element === target){
      index = i
    }

    if(nums[i] < target){
      if(target < nums[i+1]){
        sortIndex = i+1
      }
    }
  }

  return index > -1 ? index : sortIndex ? sortIndex : 0
};

var nums = [1,3,5,6], target = 3
console.log(searchInsert(nums,target))