当前位置：首页 > news >正文

【LeetCode 热题 100】35. 搜索插入位置——二分查找（闭区间）

news 2025/7/29 12:36:12

Problem: 35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(log N)
- 空间复杂度：O(1)

整体思路

这段代码同样旨在解决 “搜索插入位置 (Search Insert Position)” 的问题。它也是基于二分查找（Binary Search），但采用了另一种常见的“左闭右闭”区间模板。这个模板的搜索逻辑和边界处理与“左闭右开”版本略有不同。

算法的整体思路可以分解为以下步骤：

定义搜索区间：
- 算法使用两个指针 left 和 right 来定义一个左闭右闭的搜索区间 [left, right]。
- left 初始化为 0，right 初始化为数组的最后一个索引 nums.length - 1。这意味着初始搜索范围覆盖了整个数组的所有合法索引。
循环搜索：
- 算法的主体是一个 while (left <= right) 循环。这个条件意味着只要搜索区间 [left, right] 还不是空的（即 left 没有越过 right），搜索就继续。当 left > right 时，区间为空，循环终止。
- 在循环内部，计算中间位置 mid。这里使用了 mid = (right - left) / 2 + left 的写法，这是一种防止 left + right 整数溢出的标准做法。
- 比较与分区：将中间位置的元素 nums[mid] 与 target进行比较：
  - Case 1: nums[mid] < target: 如果中间值小于目标值，说明 target 必定在 mid 的右侧。因此，我们可以安全地排除掉 mid 及其左侧的所有元素。通过 left = mid + 1，将搜索区间更新为 [mid + 1, right]。
  - Case 2: nums[mid] >= target: 如果中间值大于或等于目标值，说明 target 可能就是 nums[mid]，或者在 mid 的左侧。在这种情况下，我们不能断定 target 不在 mid 的右侧，但可以确定答案一定不在 mid 的右侧。因此，通过 right = mid - 1，将搜索区间更新为 [left, mid - 1]。
确定最终结果：
- 循环最终会因为 left 越过 right（left = right + 1）而终止。
- 此时 left 指针的位置具有一个非常重要的含义：它指向的是数组中第一个大于 target 的元素的位置（或者如果所有元素都小于等于 target，它会指向 nums.length）。
- 为什么返回 left 是正确的？
  - target 存在：如果 target 存在，循环可能会在某一步找到 nums[mid] == target。在这种情况下，right 会变为 mid-1，left 不变，下一轮循环 left 可能会继续右移。最终，left 会停在 target 的位置或其右侧。但由于题目是求插入位置，而这个版本的二分查找最终找到的是第一个大于target的位置，所以不完全匹配。但仔细分析循环结束时的状态：left 指针左边的所有元素都 < target，right 指针右边的所有元素都 >= target。当循环结束时，left = right + 1，所以left正好是分界点，即插入位置。
  - target 不存在：left 会停在第一个比 target 大的元素的位置，这正是 target 应该插入的地方。
  - 所有元素都小于target：left 会一直右移，最终变为 nums.length，这也是正确的插入位置。
  - 所有元素都大于target：right 会一直左移，最终变为 -1，而 left 保持为 0，这也是正确的插入位置。
- 因此，直接返回 left 是该算法模板下的正确选择。

完整代码

class Solution {/*** 在一个已排序的数组中查找目标值，如果找到则返回其索引，* 否则返回它应该被插入的位置的索引。* @param nums 一个已升序排序的整数数组* @param target 目标整数* @return 目标值的索引或插入位置的索引*/public int searchInsert(int[] nums, int target) {// left: 搜索区间的左边界，初始为 0。int left = 0;// right: 搜索区间的右边界，初始为数组的最后一个索引。// 定义了一个左闭右闭的搜索区间 [left, right]。int right = nums.length - 1;// 当左边界小于或等于右边界时，搜索空间不为空，循环继续。// 循环终止条件是 left > right。while (left <= right) {// 计算中间索引。这种写法可以有效防止 (left + right) 导致的整数溢出。int mid = (right - left) / 2 + left;// 如果中间值小于目标值if (nums[mid] < target) {// 说明目标值必定在右半部分 [mid + 1, right] 中。// 更新左边界，排除 mid 及左边的所有元素。left = mid + 1;} else { // nums[mid] >= target// 说明目标值在左半部分 [left, mid - 1] 中，或者 target 就是 nums[mid]。// 更新右边界，排除 mid 及右边的所有元素。// 即使 nums[mid] == target，我们也继续向左搜索，试图找到更靠前的插入点。right = mid - 1;}}// 循环结束时，left > right。// left 指针的位置是第一个大于等于 target 的元素应该在的位置。// 这正是 target 的插入位置。return left;}
}

时空复杂度

时间复杂度：O(log N)

算法核心：该算法是二分查找。
计算依据：
- 与上一个版本类似，while 循环的每一次迭代都会将搜索区间 [left, right] 的大小（即 right - left + 1）大约减半。
- 这导致循环的迭代次数与 N 的对数成正比。
- 因此，时间复杂度为 O(log N)。