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

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

文章目录

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

整体思路

这段代码旨在解决一个经典的搜索问题：搜索插入位置 (Search Insert Position)。问题要求在一个已排序的数组 nums 中查找目标值 target。如果找到，则返回其索引；如果未找到，则返回它应该被插入的位置的索引，以保持数组的有序性。

该算法采用的核心方法是二分查找（Binary Search），这是一种在有序数据集中进行高效查找的算法。此特定实现方式是一种常见的“左闭右开”区间模板，其目标是找到第一个大于或等于 target 的元素的位置。

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

1. 定义搜索区间：

   • 算法使用两个指针 left 和 right 来定义一个左闭右开的搜索区间 [left, right)。
   • left 初始化为 0，right 初始化为数组的长度 nums.length。这意味着初始搜索范围覆盖了整个数组的所有合法索引以及末尾的插入位置。

2. 循环搜索：

   • 算法的主体是一个 while (left < right) 循环。这个条件意味着只要搜索区间 [left, right) 还不是空的（即至少包含一个元素），搜索就继续。当 left == right 时，区间为空，循环终止。
   • 在循环内部，计算中间位置 mid。
   • 比较与分区：将中间位置的元素 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 的左侧。在这种情况下，mid 本身就是一个潜在的答案（可能是第一个大于等于target的位置）。我们不能排除 mid，因此通过 right = mid，将搜索区间更新为 [left, mid)。

3. 确定最终结果：

   • 循环最终会因为 left 和 right 相遇而终止。此时，left (或 right) 指向的位置就是“插入点”。
   • 这个位置的含义是：它是数组中第一个大于或等于 target 的元素的索引。
   • 如果 target 存在于数组中，这个位置就是 target 首次出现的索引。
   • 如果 target 不存在，这个位置就是 target 应该被插入以保持数组有序的索引。
   • 因此，直接返回 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; // 当左边界小于右边界时，搜索空间不为空，循环继续。 // 循环终止条件是 left == right。 while (left < right) { // 计算中间索引。>> 1 是除以2的位运算，效率高且能防止(left+right)整数溢出。 int mid = (left + right) >> 1; // 如果中间值小于目标值 if (nums[mid] < target) { // 说明目标值必定在右半部分 [mid + 1, right) 中。 // 更新左边界，排除 mid 及左边的所有元素。 left = mid + 1; } else { // 如果中间值大于或等于目标值 // 说明目标值在左半部分 [left, mid] 中，或者 mid 本身就是目标。 // 更新右边界，将 mid 包含在新的搜索区间 [left, mid) 内作为可能的答案。 right = mid; } } // 循环结束时，left 和 right 相遇。 // 该位置就是插入点，它指向数组中第一个大于或等于 target 的元素。 // 这既是 target 的插入位置，也是当 target 存在时其首次出现的索引。 return left; }}

时空复杂度

时间复杂度：O(log N)

1. 算法核心：该算法是二分查找。
2. 计算依据：
   • 在 while 循环的每一次迭代中，搜索区间 [left, right) 的大小（即 right - left）都会被大约减半。
   • 假设初始的搜索区间大小为 N。经过 k 次迭代后，区间大小变为 N / 2^k。
   • 循环在区间大小缩减到 1 或 0 时终止，即 N / 2^k ≈ 1。
   • 解这个方程得到 2^k ≈ N，所以 k ≈ log₂(N)。
   • 由于循环的迭代次数与 N 的对数成正比，因此时间复杂度为 O(log N)。

空间复杂度：O(1)

1. 主要存储开销：算法在执行过程中，只使用了少数几个整型变量来存储状态，如 left, right, mid。
2. 计算依据：
   • 这些变量的数量是固定的，不随输入数组 nums 的大小 N 的变化而改变。
   • 算法没有创建任何新的、与输入规模成比例的数据结构（如新数组或哈希表）。

综合分析：
算法所需的额外辅助空间是常数级别的。因此，其空间复杂度为 O(1)。