知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 04 - 在排序数组中查找第一个和最后一个位置 ## 题目(LeetCode 34) 在**非递减**数组中找到 target 的起始和结束位置。 ``` 输入:nums = [5, 7, 7, 8, 8, 10], target = 8 输出:[3, 4] 输入:nums = [5, 7, 7, 8, 8, 10], target = 6 输出:[-1, -1] 输入:nums = [], target = 0 输出:[-1, -1] ``` 要求 O(log n) 时间。 ## 大白话理解 普通二分找到 target 就返回了,但现在 target 可能出现多次(连续排列),需要找到它的**左边界**和**右边界**。 做法:**二分查找 + 找到后不直接返回,继续往两边找。** ``` nums = [5, 7, 7, 8, 8, 10], target = 8 找左边界:二分找到 8 后继续往左找 找右边界:二分找到 8 后继续往右找 ``` 想象你在一个长队伍中找一群穿红衣服的人,所有人按身高排好。你找到一个红衣服的不算完,还要往左走到第一个红衣服的位置,再往右走到最后一个红衣服的位置。 ## 代码 ```java public int[] searchRange(int[] nums, int target) { int left = findLeftBound(nums, target); int right = findRightBound(nums, target); return new int[]{left, right}; } /** * 找左边界:第一个等于 target 的位置 * 找到 target 后继续往左搜 */ private int findLeftBound(int[] nums, int target) { int l = 0, r = nums.length - 1; int ans = -1; // 记录候选答案 while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] == target) { ans = mid; // 记录当前位置 r = mid - 1; // 继续往左找,看有没有更靠左的 } else if (nums[mid] < target) { l = mid + 1; } else { r = mid - 1; } } return ans; } /** * 找右边界:最后一个等于 target 的位置 * 找到 target 后继续往右搜 */ private int findRightBound(int[] nums, int target) { int l = 0, r = nums.length - 1; int ans = -1; // 记录候选答案 while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] == target) { ans = mid; // 记录当前位置 l = mid + 1; // 继续往右找,看有没有更靠右的 } else if (nums[mid] < target) { l = mid + 1; } else { r = mid - 1; } } return ans; } ``` > 💬 **Q:为什么 leftBound 和 rightBound 只有一行不同?** > > 核心就是:找到 target 后往哪边继续搜。 > - leftBound:`r = mid - 1`(继续往左压缩) > - rightBound:`l = mid + 1`(继续往右扩展) > > 其他部分完全一样。 ## 另一种写法:使用 lowerBound 思想 更简洁,一次搞懂两个边界: ```java public int[] searchRange(int[] nums, int target) { // 找第一个 >= target 的位置 int left = lowerBound(nums, target); // 如果 left 越界或者 nums[left] != target,说明 target 不存在 if (left == nums.length || nums[left] != target) { return new int[]{-1, -1}; } // 找第一个 > target 的位置,右边界 = 它 - 1 int right = lowerBound(nums, target + 1) - 1; return new int[]{left, right}; } private int lowerBound(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] >= target) { r = mid - 1; } else { l = mid + 1; } } return l; } ``` ``` 原理: left = lowerBound(nums, target) → 第一个 >= target 的位置 right = lowerBound(nums, target+1)-1 → 第一个 >= (target+1) 的位置 - 1 = 最后一个 == target 的位置 nums = [5, 7, 7, 8, 8, 10], target = 8 lowerBound(nums, 8) → 第一个 >= 8 的位置 = 3 → left = 3 lowerBound(nums, 9) → 第一个 >= 9 的位置 = 5 → right = 5-1 = 4 答案:[3, 4] ✓ ``` ## 过程模拟:两次二分法 ``` nums = [5, 7, 7, 8, 8, 10], target = 8 索引: 0 1 2 3 4 5 ═══════════════════════════════════ 找左边界: ═══════════════════════════════════ 初始: l=0, r=5, ans=-1 第1轮: mid=2, nums[2]=7 < 8 → l=3 [5, 7, 7, 8, 8, 10] l→ 第2轮: mid=4, nums[4]=8 == 8 → ans=4, r=3 [5, 7, 7, 8, 8, 10] r← 第3轮: mid=3, nums[3]=8 == 8 → ans=3, r=2 [5, 7, 7, 8, 8, 10] r← 第4轮: l=3, r=2 → l > r 退出 ans = 3 → 左边界 = 3 ✓ ═══════════════════════════════════ 找右边界: ═══════════════════════════════════ 初始: l=0, r=5, ans=-1 第1轮: mid=2, nums[2]=7 < 8 → l=3 第2轮: mid=4, nums[4]=8 == 8 → ans=4, l=5 第3轮: mid=5, nums[5]=10 > 8 → r=4 第4轮: l=5, r=4 → l > r 退出 ans = 4 → 右边界 = 4 ✓ 答案:[3, 4] ✓ ``` ## 过程模拟:target 不存在的情况 ``` nums = [5, 7, 7, 8, 8, 10], target = 6 找左边界: 第1轮: l=0, r=5, mid=2 → 7 > 6 → r=1 第2轮: l=0, r=1, mid=0 → 5 < 6 → l=1 第3轮: l=1, r=1, mid=1 → 7 > 6 → r=0 l=1, r=0 → 退出, ans 始终为 -1 左边界 = -1,直接返回 [-1, -1] ✓ ``` ## 复杂度 - 时间:O(log n),两次二分各 O(log n) = O(log n) - 空间:O(1) ## 一句话总结 两次二分:找到 target 后,左边界的继续往左搜(`r = mid-1`),右边界的继续往右搜(`l = mid+1`)。或者用 `lowerBound(nums, target)` 一次搞定左边界,`lowerBound(nums, target+1)-1` 搞定右边界。 --- 上一篇:[03 - 寻找旋转数组最小值](./03-find-min-rotated.md) | 下一篇:[05 - 搜索插入位置](./05-search-insert.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入