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

Leetcode二分查找（3）

ai 2025/9/3 13:27:38

34. 在排序数组中查找元素的第一个和最后一个位置

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

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

解题思路总览

  1. 双二分（lower_bound / upper_bound 分离）
  2. 双指针式收缩二分（分别找左边界与右边界的另一种写法）
  3. 递归二分同时搜两端（分治递归版）
  4. 先标准二分再向两侧线性扩展（不满足最坏 O(log n)，仅作对比）
  5. 利用 Arrays.binarySearch 辅助再找边界（最坏 O(n)，仅作对比）

说明：题目要求时间复杂度 O(log n)。满足该要求的为：方法1、方法2、方法3。方法4、5 仅用于思路拓展与错误实践分析，实际面试应避免使用（或需额外说明均摊/期望场景）。

思路一：双二分（lower_bound / upper_bound 分离）

原理与适用场景：
利用二分查找有序数组中“第一个 >= target 的位置”（lower_bound）与“第一个 > target 的位置”（upper_bound）。若 lower_bound 下标超界或对应元素不等于 target，说明不存在。否则答案为 [lower_bound, upper_bound - 1]。该模式稳定、语义清晰，是最推荐写法。适用任何需要找区间边界的非递减排序数组问题，比如统计出现次数、插入位置计算等。

实现步骤：

  1. 定义函数 lowerBound(nums, target)：二分寻找第一个 >= target 的索引。
  2. 定义函数 upperBound(nums, target)：二分寻找第一个 > target 的索引。
  3. 调用 lb = lowerBound(nums, target)。若 lb == n 或 nums[lb] != target -> 返回 [-1,-1]。
  4. 调用 ub = upperBound(nums, target)。返回 [lb, ub-1]。
  5. 全部过程每个二分 O(log n)。

JAVA 代码实现：

public class SolutionBounds {// 主函数：返回 target 在有序数组中的起止下标public int[] searchRange(int[] nums, int target) {int n = nums.length; // 数组长度int lb = lowerBound(nums, target); // 第一个 >= target 的位置// 若 lb 超界或 lb 位置的值不等于 target，说明不存在if (lb == n || nums[lb] != target) {return new int[]{-1, -1};}int ub = upperBound(nums, target); // 第一个 > target 的位置return new int[]{lb, ub - 1}; // 右边界 = ub - 1}// lower_bound: 找到第一个 >= target 的索引private int lowerBound(int[] a, int target) {int l = 0;              // 左闭int r = a.length;       // 右开（半开区间 [l, r)）while (l < r) {         // 区间非空继续int mid = l + (r - l) / 2; // 避免 (l+r) 可能的溢出if (a[mid] >= target) {    // mid 位置已经满足 >= target，压缩右端r = mid;} else {                   // a[mid] < target 需要右移l = mid + 1;}}return l; // 或 r，循环结束 l == r}// upper_bound: 找到第一个 > target 的索引private int upperBound(int[] a, int target) {int l = 0;int r = a.length;while (l < r) {int mid = l + (r - l) / 2;if (a[mid] > target) { // mid 已经严格大于 target，右端缩到 midr = mid;} else {               // a[mid] <= target，需要继续往右找l = mid + 1;}}return l; // 返回第一个 > target 的位置}
}

思路二：双指针式收缩二分（分别找左边界/右边界的另一种写法）

原理与适用场景：
与思路一本质相同，但采用“寻找特定边界”语义化条件：

  1. 找左边界：在 nums[mid] >= target 时继续向左收缩，保证最终落在最左的 target。
  2. 找右边界：在 nums[mid] <= target 时继续向右收缩，最终落在最右 target。
    写法上多用 (l <= r) 形式并保存答案变量 res。适合已经熟悉普通二分的人过渡到边界二分。

实现步骤：

  1. left = findLeft(nums, target) 使用经典 while(l <= r)。
  2. 若 left == -1（未找到）返回 [-1,-1]。
  3. right = findRight(nums, target)。
  4. 返回 [left, right]。

JAVA 代码实现：

public class SolutionShrink {public int[] searchRange(int[] nums, int target) {int left = findLeft(nums, target); // 查找最左出现if (left == -1) {                  // 没找到直接返回return new int[]{-1, -1};}int right = findRight(nums, target); // 查找最右出现return new int[]{left, right};}// 查找最左边界private int findLeft(int[] a, int target) {int l = 0;int r = a.length - 1;int ans = -1;             // 记录答案while (l <= r) {          // 闭区间写法int mid = l + (r - l) / 2;if (a[mid] >= target) { // mid 可能是左边界，记录并继续左侧搜索if (a[mid] == target) {ans = mid;    // 暂存候选}r = mid - 1;      // 收缩右端} else {               // a[mid] < target，只能去右侧l = mid + 1;}}return ans;}// 查找最右边界private int findRight(int[] a, int target) {int l = 0;int r = a.length - 1;int ans = -1;while (l <= r) {int mid = l + (r - l) / 2;if (a[mid] <= target) { // mid 可能是右边界if (a[mid] == target) {ans = mid;     // 记录候选}l = mid + 1;       // 继续右侧} else {                // a[mid] > target 只能去左侧r = mid - 1;}}return ans;}
}

思路三：递归二分同时搜两端（分治递归版）

原理与适用场景：
递归拆分区间 [l,r]：

  1. 若 nums[mid] == target：向左右延展继续递归，合并得最左与最右位置。
  2. 若 nums[mid] > target：仅递归左半。
  3. 若 nums[mid] < target：仅递归右半。
    剪枝：当区间最小值 > target 或最大值 < target 可直接终止，提升常数。最坏仍 O(log n)（找到后左右延展以二分方式探索边界，不做线性扫描）。
    适合想用递归风格写法的场景，便于与其它分治模板统一。

实现步骤：

  1. 定义递归函数 dfs(nums, l, r, target) 返回 int[]{left,right} 或 {-1,-1}。
  2. 剪枝：若 l>r 或 target 不在 [nums[l], nums[r]] 范围，返回 {-1,-1}。
  3. 计算 mid。
  4. nums[mid] == target：分别向左右递归并合并边界（当前 mid 也纳入）。
  5. 根据大小关系单侧递归。
  6. 初始调用并返回。

JAVA 代码实现：

public class SolutionRecursive {public int[] searchRange(int[] nums, int target) {if (nums == null || nums.length == 0) { // 空数组直接返回return new int[]{-1, -1};}return dfs(nums, 0, nums.length - 1, target);}private int[] dfs(int[] a, int l, int r, int target) {if (l > r) {                 // 区间为空return new int[]{-1, -1};}if (a[l] > target || a[r] < target) { // 剪枝：整体不可能包含 targetreturn new int[]{-1, -1};}int mid = l + (r - l) / 2;  // 中点if (a[mid] == target) {     // 命中，向左右扩展（递归二分方式）int left = mid;int right = mid;// 向左递归继续找更左位置int[] leftPart = dfs(a, l, mid - 1, target);if (leftPart[0] != -1) { // 左侧找到至少一个 targetleft = leftPart[0];}// 向右递归继续找更右位置int[] rightPart = dfs(a, mid + 1, r, target);if (rightPart[1] != -1) { // 右侧找到right = rightPart[1];}return new int[]{left, right};} else if (a[mid] > target) { // 只可能在左半return dfs(a, l, mid - 1, target);} else {                      // a[mid] < target 只可能在右半return dfs(a, mid + 1, r, target);}}
}

思路四：先标准二分定位一个 target 再向两侧线性扩展（不满足最坏 O(log n)）

原理与适用场景：
先普通二分找任意一个 target 索引 pos，然后从 pos 向左、向右 while 扫描直到值不等于 target。若 target 大量集中（例如全部元素都相等），两侧扩展会退化为 O(n)。因此最坏不满足题目约束，面试中通常不被接受，除非可额外说明数据分布稀疏、期望复杂度需求。列出此法用于对比“线性扩展风险”。

实现步骤（简述）：

  1. 二分找一个出现位置 pos。
  2. 若未找到返回 [-1,-1]。
  3. i=pos 向左减，j=pos 向右增，直到越界或不等。
  4. 返回 [i+1, j-1]。

复杂度：最坏 O(n)。

思路五：利用 Arrays.binarySearch + 再找边界（最坏 O(n)）

原理与适用场景：
调用 Java 标准库 Arrays.binarySearch 得到任意一个匹配位置，然后再像思路四一样线性扩展。其性能瓶颈与思路四相同。优点是初始定位代码更短。仍不满足最坏 O(log n)。

实现步骤（简述）：

  1. pos = Arrays.binarySearch(nums, target)。
  2. pos < 0 -> [-1,-1]。
  3. 线性左右扩展。

补充说明（对比分析）

  1. 正确满足 O(log n) 的方案：

    • 思路一（双二分）：实现最简洁，可复用 lower/upper 模板，易于扩展到统计次数（ub - lb）。
    • 思路二（收缩式）：与思路一复杂度相同，适合从“普通二分”过渡到“边界二分”的人群；需要多个 ans 变量。
    • 思路三（递归分治）：逻辑清晰，可与其他递归模板统一，但递归深度 O(log n)，有函数栈开销，迭代更高效。

  2. 不满足最坏 O(log n)（仅学习对比）：

    • 思路四、五：在目标元素占多数时扩展 O(n)，示例：nums=[2,2,2,2,2], target=2。

  3. 时间复杂度：

    • 思路一：O(log n)
    • 思路二：O(log n)
    • 思路三：O(log n)
    • 思路四：最坏 O(n)
    • 思路五：最坏 O(n)

  4. 空间复杂度：

    • 思路一：O(1)
    • 思路二：O(1)
    • 思路三：O(log n)（递归栈）
    • 思路四：O(1)
    • 思路五：O(1)

  5. 代码健壮性注意点：

    • mid 计算使用 mid = l + (r - l) / 2 避免整数溢出。
    • 检查数组为空（length == 0）直接返回 [-1,-1]。
    • 注意区分不同区间表示法：半开 [l,r) vs 闭区间 [l,r]，不能混用。

  6. 推荐结论：

    • 首选思路一（lower/upper 模板）。
    • 若不熟悉半开区间，可用思路二（闭区间写法）逐步过渡。
    • 递归仅在希望统一分治风格时使用。

  7. 测试用例建议：

    • 普通：nums=[5,7,7,8,8,10], target=8 -> [3,4]
    • 不存在：nums=[5,7,7,8,8,10], target=6 -> [-1,-1]
    • 全部相同：nums=[2,2,2,2], target=2 -> [0,3]
    • 单元素匹配：nums=[1], target=1 -> [0,0]
    • 单元素不匹配：nums=[1], target=0 -> [-1,-1]
    • 边界在首：nums=[3,3,3,4,5], target=3 -> [0,2]
    • 边界在尾：nums=[1,2,2,2], target=2 -> [1,3]
    • 大量重复及空数组：nums=[], target=1 -> [-1,-1]

综上，使用双二分模板能最直接、稳定地满足题目对 O(log n) 的要求，是最具可维护性的实现方式。

http://www.xdnf.cn/news/19656.html

相关文章：

  • 移动硬盘删除东西后，没有释放空间
  • 【机器学习入门】5.2 回归的起源——从身高遗传到线性模型的百年演变
  • 狄利克雷分布作用
  • CentOS 创建站点
  • 二进制流进行预览pdf、excel、docx
  • Cisco FMC利用sftp Server拷贝文件方法
  • 0902 C++类的匿名对象
  • 面试问题：c++的内存管理方式，delete的使用，vector的resize和reverse，容量拓展
  • uni-app 布局之 Flex
  • 基于STM32与华为云联动的智能电动车充电桩管理系统
  • QSlider 和 QProgressBar 的区别与实践
  • 【Linux基础】Linux系统启动：深入解析Linux系统启动完整流程
  • 仿真波导中超短脉冲传输中的各种非线性效应所产生的超连续谱
  • AI如何理解PDF中的表格和图片？
  • qt安装FFmpeg后编译遇到error: collect2.exe: error: ld returned 1 exit status错误
  • 链表题类型注解解惑：理解Optional，理解ListNode
  • 数据结构--跳表（Skip List）
  • 【学Python自动化】 7. Python 输入与输出学习笔记
  • kaggle中的2D目标检测训练trick总结
  • 用了企业微信 AI 半年，这 5 个功能让我彻底告别重复劳动
  • 一文带你入门 AT 指令集：从串口通信到模块控制
  • 【智能体开发】怎样提升AI智能体的运行速度？
  • 实验2-代理模式和观察者模式设计
  • C++全局变量未初始的和已初始化的位置放在哪里？
  • C语言————实战项目“扫雷游戏”(完整代码)
  • 【Spring Cloud微服务】9.一站式掌握 Seata：架构设计与 AT、TCC、Saga、XA 模式选型指南
  • MD5加密算法详解与实现
  • 【LeetCode_26】删除有序数组中的重复项
  • 手撕Redis底层2-网络模型深度剖析
  • 云电脑是什么？与普通电脑的区别在哪里？——天翼云电脑体验推荐