68. 查找插入位置
68. 查找插入位置
题目
给定一个排序的整数数组 nums
和一个整数目标值 target
,请在数组中找到 target
,并返回其下标。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums
为无重复元素 的升序 排列数组-10^4 <= target <= 10^4
注意
本题与 LeetCode 第 35 题 相同。
解题思路
可以使用 二分查找法 来解决这个问题,二分查找的思路是每次将数组分成两半,逐步缩小查找范围 [left, right]
,如果找到与 target
相等的数就返回 mid
,否则返回 left
。
- 初始化两个指针
left
和right
,分别指向数组的左右两端。 - 计算中间位置
mid
,比较nums[mid]
和target
:- 如果
nums[mid] == target
,返回mid
,即target
的索引位置。 - 如果
nums[mid] < target
,说明target
应该在右半部分,移动left
指针到mid + 1
。 - 如果
nums[mid] > target
,说明target
应该在左半部分,移动right
指针到mid - 1
。
- 如果
- 如果遍历完数组仍未找到
target
,则返回left
,此时left
就是target
应该插入的位置。
复杂度分析
- 时间复杂度:
O(log n)
,每次查找都会将数组的查找范围缩小一半。 - 空间复杂度:
O(1)
,只使用了常数级别的额外空间
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function (nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((right + left) / 2);
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return left;
};