LeetCode搜索插入位置

题目描述

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

请必须使用时间复杂度为 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

解题思路

二分查找的时间复杂度是 O(log n)，其中 n 是数组的长度。所以可实现一个二分查找算法，用于在排序数组中查找一个目标值，并返回目标值的索引或者它应该被插入的位置。

代码

/*** @param {number[]} nums* @param {number} target* @return {number}*/
var searchInsert = function(nums, target) {let left = 0, right = nums.length - 1; // 闭区间 [left, right]while (left <= right) { // 区间不为空// 循环不变量：// nums[left-1] < target// nums[right+1] >= targetconst mid = Math.floor((left + right) / 2);if (nums[mid] < target) {left = mid + 1; // 范围缩小到 [mid+1, right]} else {right = mid - 1; // 范围缩小到 [left, mid-1]}}return left;
}

代码分析

1. 初始化两个指针 left 和 right，分别指向数组的起始和结束位置，形成一个闭区间 [left, right]。

2. 进入一个 while 循环，条件是 left 小于等于 right，即区间不为空。

3. 在循环内部，计算中间位置 mid，使用 Math.floor((left + right) / 2) 来确保 mid 是一个整数。

4. 比较 nums[mid] 和 target 的值：

   • 如果 nums[mid] 小于 target，则说明 target 可能在 mid 的右侧，因此更新 left 为 mid + 1，这样新的搜索区间就变成了 [mid + 1, right]。
   • 如果 nums[mid] 大于或等于 target，则说明 target 可能在 mid 的左侧或 mid 本身，因此更新 right 为 mid - 1，这样新的搜索区间就变成了 [left, mid - 1]。

5. 当 while 循环结束时，left 指针将指向 target 应该被插入的位置。如果 target 在数组中存在，left 将指向 target 的索引；如果 target 不存在，left 将指向 target 应该被插入的位置，以保持数组的排序。

6. 最后，函数返回 left 作为结果。

这个算法的关键在于，每次迭代都会将搜索区间减半，这是通过比较中间元素和目标值来实现的。如果目标值在数组中，算法最终会找到它；如果目标值不在数组中，算法会找到目标值应该被插入的位置，以保持数组的排序。

这里可以自行走一遍示例，因为最后返回的是left，而判断最后是因为right减少导致循环结束，所以得到正确结果