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] >= target
        const 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减少导致循环结束，所以得到正确结果

原文地址：https://blog.csdn.net/weixin_55608297/article/details/142927428

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！