35. 搜索插入位置

🟢   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5

Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2

Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7

Output: 4

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

题目大意

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

解题思路

可以使用 二分查找法 来解决这个问题，二分查找的思路是每次将数组分成两半，逐步缩小查找范围 [left, right]，如果找到与 target 相等的数就返回 mid ，否则返回 left。

1. 初始化两个指针 left 和 right，分别指向数组的左右两端。
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;
};

相关题目

题号	标题	题解	标签	难度
278	第一个错误的版本	[✓]	二分查找 交互
3065	超过阈值的最少操作数 I		数组