跳至主要內容

68. 查找插入位置


68. 查找插入位置

🟢   🔖  数组 二分查找  🔗 力扣open in new window

题目

给定一个排序的整数数组 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

  1. 初始化两个指针 leftright,分别指向数组的左右两端。
  2. 计算中间位置 mid,比较 nums[mid]target
    • 如果 nums[mid] == target,返回 mid,即 target 的索引位置。
    • 如果 nums[mid] < target,说明 target 应该在右半部分,移动 left 指针到 mid + 1
    • 如果 nums[mid] > target,说明 target 应该在左半部分,移动 right 指针到 mid - 1
  3. 如果遍历完数组仍未找到 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;
};