# 35. 搜索插入位置 (opens new window)
# 题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构 (opens new window)，而且表中元素按关键字有序排列。它的基本思想是：（这里假设数组元素呈升序排列）将 n 个元素分成个数大致相同的两半，取 a[n/2]与欲查找的 x 作比较，如果 x=a[n/2]则找到 x，算法终止；如 果 x < a[n/2]，则我们只要在数组 (opens new window)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);
}
}
# 全部代码
/*
* @lc app=leetcode.cn id=35 lang=javascript
*
* [35] 搜索插入位置
*
* https://leetcode-cn.com/problems/search-insert-position/description/
*
* algorithms
* Easy (46.69%)
* Likes: 1029
* Dislikes: 0
* Total Accepted: 465.4K
* Total Submissions: 996.8K
* Testcase Example: '[1,3,5,6]\n5'
*
* 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
*
* 请必须使用时间复杂度为 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
*
*
* 示例 4:
*
*
* 输入: nums = [1,3,5,6], target = 0
* 输出: 0
*
*
* 示例 5:
*
*
* 输入: nums = [1], target = 0
* 输出: 0
*
*
*
*
* 提示:
*
*
* 1
* -10^4
* nums 为无重复元素的升序排列数组
* -10^4
*
*
*/
// @lc code=start
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
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;
};
// @lc code=end
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;
};
//这个版本少用了一个变量，按理说内存消耗应该减少才对，玄学
var searchInsert = function(nums, target) {
for(let i=0;i<nums.length;i++){
if(nums[i]>=target){
return i;
}
}
//考虑插到末尾的情况
return nums.length;
};
//这个写法是最精简的，绝妙之处在于将判断条件和循环条件融合在了一起，
//其实上边的for循环也可以这样做，这样就不必使用break语句了
var searchInsert = function(nums, target) {
let i=0;
while(i<nums.length&&nums[i]<target){
i++;
}
return i
};
//循环
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
};
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
};
//递归，递归需要建立递归调用栈，所以一般比循环的用时和内存消耗都多
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)
}
}