原题地址：搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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
二分查找
由于数组已经有序，可以采用二分查找，只需要处理好最后查找失败时的情形即可：
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
const searchInsert1 = function(nums, target) {
// 二分查找的左中右端点
let [left, right, middle] = [0, nums.length - 1];
while (left < right) {
middle = Math.floor((left + right) / 2);
// 查找成功
if (nums[middle] === target) {
return middle;
}
if (nums[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
// 查找失败，判断最后失败的位置的数值与target的大小来决定插入到左边还是右边
return nums[left] < target ? left + 1 : left;
};
测试：
let start = new Date();
const test = searchInsert1;
console.log(test([1,3,5,8], 5)); // 2
console.log(test([1,3,5,8], 2)); // 1
console.log(test([1,3,5,6], 7)); // 4
console.log(test([1,3,5,8], 0)); // 0
console.log(test([1,3], 2)); // 1
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 二分查找，时间复杂度为$O(logn)$
空间复杂度： 空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 4,2019