搜索插入位置
🟢 简单题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
示例 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提示
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums为无重复元素的升序排列数组-10^4 <= target <= 10^4
解法
参考答案 (2 个标签)
二分查找 O(log n)
思路
找到第一个大于等于 target 的位置。
代码实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
function searchInsert(nums, target) {
let left = 0;
let right = nums.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}复杂度分析
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
关键点
- 右边界为 nums.length：target 可能插入末尾
- 循环条件
left < right：左闭右开区间 right = mid：mid 可能是答案