【LeetCode 热题 100】34. 在排序数组中查找元素的第一个和最后一个位置——二分查找

Problem: 34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

文章目录

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

整体思路

这段代码旨在解决一个经典的搜索问题：在排序数组中查找元素的第一个和最后一个位置 (Find First and Last Position of Element in Sorted Array)。问题要求在一个升序排序的数组 nums 中，找到给定目标值 target 的起始位置和结束位置。如果 target 不存在，则返回 [-1, -1]。

该算法采用了一种非常精妙和通用的方法：两次二分查找。它将原问题分解为两个子问题：

1. 查找 target 的下界 (Lower Bound)，即第一个大于或等于 target 的元素的位置。
2. 查找 target + 1 的下界，即第一个大于或等于 target + 1 的元素的位置。

通过这两个下界，就可以巧妙地推导出 target 的起始和结束位置。

1. lowerBound 辅助函数：

   • 这是算法的核心。它实现了一个标准的二分查找，其目标是找到一个值 val 的下界。
   • 它采用“左闭右开”区间 [left, right) 的模板。
   • 循环的逻辑是：如果 nums[mid] < val，则下界一定在 mid 右侧；如果 nums[mid] >= val，则 mid 本身可能是下界，或者下界在 mid 左侧。
   • 最终返回的 left 值，就是数组中第一个大于或等于 val 的元素的索引。这个函数是解决一类“查找边界”问题的通用工具。

2. 查找起始位置 (left)：

   • 直接调用 lowerBound(nums, target)。根据 lowerBound 的定义，它返回的就是第一个大于或等于 target 的元素的位置。
   • 如果 target 存在，这个位置就是 target 的起始位置。

3. 处理 target 不存在的情况：

   • 在找到起始位置 left 后，必须进行一次校验。
   • if (left == nums.length || nums[left] != target):
     • left == nums.length: lowerBound 返回数组长度，说明数组中所有元素都小于 target。
     • nums[left] != target: lowerBound 返回了一个位置，但该位置的元素不是 target（而是第一个比target大的元素）。
   • 如果满足以上任一条件，说明 target 在数组中不存在，直接返回 [-1, -1]。

4. 查找结束位置 (right)：

   • 这一步是算法最巧妙的地方。它通过查找 target + 1 的下界来间接确定 target 的上界。
   • 调用 lowerBound(nums, target + 1) 会返回第一个大于或等于 target + 1 的元素的位置。
   • 这个位置，恰好就是 target 这个值在数组中可能出现的最右位置的再下一个位置。
   • 因此，target 的结束位置就是 lowerBound(nums, target + 1) - 1。

5. 合成并返回结果：

   • 将计算出的起始位置 left 和结束位置 right - 1 组合成一个数组 [left, right - 1] 并返回。

完整代码

class Solution { /** * 在一个已排序的数组中查找目标值的起始和结束位置。 * @param nums 一个已升序排序的整数数组 * @param target 目标整数 * @return 包含起始和结束位置的数组，如果不存在则返回 [-1, -1] */ public int[] searchRange(int[] nums, int target) { // 步骤 1: 使用 lowerBound 查找 target 的起始位置。 // left 指向第一个 >= target 的元素。 int left = lowerBound(nums, target); // 步骤 2: 校验 target 是否存在于数组中。 // 如果 left 越界，或者 left 指向的元素不等于 target，说明 target 不存在。 if (left == nums.length || nums[left] != target) { return new int[]{-1, -1}; } // 步骤 3: 使用 lowerBound 查找 target 的结束位置。 // 这里的技巧是查找 target + 1 的下界。 // right 指向第一个 >= target + 1 的元素。 // 这个位置的前一个位置，就是 target 的最后一个出现位置。 int right = lowerBound(nums, target + 1); // 步骤 4: 合成并返回结果。 // 起始位置是 left，结束位置是 right - 1。 return new int[]{left, right - 1}; } /** * 二分查找辅助函数，用于查找 target 的下界（Lower Bound）。 * @param nums 排序数组 * @param target 目标值 * @return 数组中第一个大于或等于 target 的元素的索引。如果所有元素都小于target，则返回 nums.length。 */ private int lowerBound(int[] nums, int target) { // 采用左闭右开的搜索区间 [left, right) int left = 0; int right = nums.length; while (left < right) { // 防止 (left + right) 溢出 int mid = left + (right - left) / 2; // 如果中间值小于目标值，则下界一定在右侧 if (nums[mid] < target) { left = mid + 1; } else { // nums[mid] >= target // 如果中间值大于或等于目标值，则 mid 可能是下界，或者下界在左侧 right = mid; } } // 循环结束时，left 就是第一个 >= target 的位置 return left; }}

时空复杂度

时间复杂度：O(log N)

1. 算法核心：该算法的主体是两次调用 lowerBound 函数，而 lowerBound 本身是一个标准的二分查找。
2. 计算依据：
   • 第一次调用 lowerBound(nums, target) 的时间复杂度是 O(log N)。
   • 第二次调用 lowerBound(nums, target + 1) 的时间复杂度也是 O(log N)。
   • 其余操作（校验、数组创建）都是 O(1) 的。

综合分析：
算法的总时间复杂度是 O(log N) + O(log N) = O(2 * log N)。在 Big O 表示法中，常数因子被忽略，因此最终的时间复杂度为 O(log N)。

空间复杂度：O(1)

1. 主要存储开销：算法在执行过程中，只使用了少数几个整型变量来存储状态，如 left, right, mid。
2. 计算依据：
   • 这些变量的数量是固定的，不随输入数组 nums 的大小 N 的变化而改变。
   • 返回的结果数组 new int[]{-1, -1} 或 new int[]{left, right - 1} 的大小是固定的2，不计入辅助空间复杂度。

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