35. 搜索插入位置

小目标：百篇题解之一，破百开源成库。关注我（牛客、Github、力扣），即可获取最新题解。

题目描述

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

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

示例 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

相关信息：

难度：简单
标签：数组、二分查找

题解

方法一：简单查找

简单查找就是使用一个循环从头到尾去遍历一个有序数组，找出第一个大于等于目标值的元素的下标，遍历完也没找到就返回元素下标。

JavaScript 实现

以下所有版本的代码为从上至下依次迭代优化的成果。

//执行用时: 124 ms
//内存消耗: 38.9 MB
var searchInsert = function(nums, target) {
    let out;
  for(let i=0;i<nums.length;i++){
        if(nums[i]>=target){
            out=i;
            break;
        }
    //是否插到末尾
        if(i==nums.length-1){
            out=nums.length;
        }
    /*执行用时比较长就是因为在循环中对每个元素都进行了末尾的判断，
    其实完全可以将其放在循环之后，以此减少每次循环的执行时间*/
    }
    return out;
};

/*
执行用时: 76 ms
内存消耗: 38.7 MB
*/
//这个版本的代码是效率最高的，后面几个版本的代码优化的写法，
//但是效率没有这个版本高，可能leetcode的测试也是有误差的吧
var searchInsert = function(nums, target) {
    let out=-1;
  for(let i=0;i<nums.length;i++){
        if(nums[i]>=target){
            out=i;
            break;
        }
    }
    //考虑插到末尾的情况
        if(out==-1){
            return nums.length;
        }
    return out;
};

/*
执行用时: 84 ms
内存消耗: 39.1 MB
*/
//这个版本少用了一个变量，按理说内存消耗应该减少才对，玄学
var searchInsert = function(nums, target) {
  for(let i=0;i<nums.length;i++){
        if(nums[i]>=target){
            return i;
        }
    }
    //考虑插到末尾的情况
    return nums.length;
};

/*
执行用时: 88 ms
内存消耗: 38.9 MB
*/
//这个写法是最精简的，绝妙之处在于将判断条件和循环条件融合在了一起，
//其实上边的for循环也可以这样做，这样就不必使用break语句了
var searchInsert = function(nums, target) {
  let i=0;
  while(i<nums.length&&nums[i]<target){
      i++;
  }
  return i
};

方法二：二分查找

注意题目提供的是一个有序数组，所以应该想到使用二分法。

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。它的基本思想是：（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如果x < a[n/2]，则我们只要在数组a的左半部继续搜索x；如果x > a[n/2]，则我们只要在数组a的右半部继续搜索x。

二分查找可以有循环和递归两种实现方法。

JavaScript 实现

/*
执行用时: 88 ms
内存消耗: 38.9 MB
*/
//循环
var searchInsert = function(nums, target) {
 let right=0;
 let left=nums.length-1;
 while(right<=left){
     let middle =(right+left)>>>1//使用位运算取整
     if(nums[middle]===target){
         return middle;
     }else if(target>nums[middle]){
         right=middle+1
     }else{
         left=middle-1
     }
 }
 return right;// 退出循环时 hi比lo小1
};

/*
执行用时: 72 ms
内存消耗: 38.8 MB
*/
var searchInsert = function(nums, target) {
 let right=0;
 let left=nums.length-1;
  //可将插入数组头部和尾部的情况单独处理，以此来提升程序执行用时。
 if(target > nums[left]) return left+1
 else if(target < nums[0]) return 0

 while(right<=left){
     let middle =(right+left)>>>1
     if(nums[middle]===target){
         return middle;
     }else if(target>nums[middle]){
         right=middle+1
     }else{
         left=middle-1
     }
 }
 return right;// 退出循环时 hi比lo小1
};

/*
执行用时: 100 ms
内存消耗: 39 MB
*/
//递归，递归需要建立递归调用栈，所以一般比循环的用时和内存消耗都多
var searchInsert = function (nums, target) {
    let left = 0;
    let right = nums.length - 1;
    return binarySearch(left, right, nums, target)
};

function binarySearch(left, right, nums, target) {
    if (left > right) {
        return left;
    }
    let mid = parseInt((left + right) / 2);
    if (target === nums[mid]) {
        return mid;
    } else if (target > nums[mid]) {
        return binarySearch(mid + 1, right, nums, target)
    } else {
        return binarySearch(left, mid - 1, nums, target)
    }
}

最后，如果本文对你有所帮助的话，不要忘了给我点赞三连嗷～感谢！

【35. 搜索插入位置】题解

35. 搜索插入位置

题目描述

题解

方法一：简单查找

JavaScript 实现

方法二：二分查找

JavaScript 实现