第一部分：题目描述
🏠 链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
⭐ 难度：中等
第二部分：思路分析
需要使用 最靠左索引 与 最靠右索引 解决该问题。
- 最靠左索引：搜索目标值为 target 且 索引最小的索引位置
- 最靠右索引：搜索目标值为 target 且 索引最大的索引位置
📝 以 最靠左索引 为例来说明：
- 我们知道普通的二分查找是找到一个 目标值 就停止搜索，返回 中间索引 就可以了。
- 但这里我们需要查找 索引最小的索引位置，那么即使查找到了一个目标值不能直接返回，应该记录下当前的目标值对应的索引，即中间索引mid。
- 同时，查找到了这个目标值，我们应该缩小搜索的右边范围，既查找 当前mid索引 左边的范围。
- 即 需要设置
right = mid - 1。
同理，最靠右索引也需要记录 每次查找到的索引，同时缩小搜索的左边范围，即设置 left = mid + 1。
第三部分：代码实现
class Solution { public int[] searchRange(int[] nums, int target) { // 查找最小索引 int minIndex = searchMinIndex(nums, target); // 如果未搜索到说明数组不存在目标值 if (minIndex == -1) { return new int[]{-1, -1}; } // 查找最大索引 int maxIndex = searchMaxIndex(nums, target); return new int[]{minIndex, maxIndex}; } private int searchMinIndex(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 记录最小索引 int minIndex = -1; int mid; while (left <= right) { // 无符号右移 代替 /2 操作，避免 left + right 的超出 int能取的最大值 mid = (left + right) >>> 1; if (target < nums[mid]) { // 如果 目标值 小于 中间值 right = mid - 1; } else if (nums[mid] < target) { // 如果 目标值 大于 中间值 left = mid + 1; } else { // 记录当前中间索引为最小索引 minIndex = mid; // 缩小右范围，以便能向左查找更小的索引 right = mid - 1; } } return minIndex; } private int searchMaxIndex(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 记录最大索引 int maxIndex = -1; int mid; while (left <= right) { // 无符号右移 代替 /2 操作，避免 left + right 的超出 int能取的最大值 mid = (left + right) >>> 1; if (target < nums[mid]) { // 如果 目标值 小于 中间值 right = mid - 1; } else if (nums[mid] < target) { // 如果 目标值 大于 中间值 left = mid + 1; } else { // 记录当前中间索引为最大索引 maxIndex = mid; // 缩小左范围，以便能向右查找更大的索引 left = mid + 1; } } return maxIndex; } }
public int[] searchRange(int[] nums, int target) { // 查找最小索引 int minIndex = searchMinIndex(nums, target); // 如果未搜索到说明数组不存在目标值 if (minIndex == -1) { return new int[]{-1, -1}; } // 查找最大索引 int maxIndex = searchMaxIndex(nums, target); return new int[]{minIndex, maxIndex}; } private int searchMinIndex(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 记录最小索引 int minIndex = -1; int mid; while (left <= right) { // 无符号右移 代替 /2 操作，避免 left + right 的超出 int能取的最大值 mid = (left + right) >>> 1; if (target < nums[mid]) { // 如果 目标值 小于 中间值 right = mid - 1; } else if (nums[mid] < target) { // 如果 目标值 大于 中间值 left = mid + 1; } else { // 记录当前中间索引为最小索引 minIndex = mid; // 缩小右范围，以便能向左查找更小的索引 right = mid - 1; } } return minIndex; } private int searchMaxIndex(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 记录最大索引 int maxIndex = -1; int mid; while (left <= right) { // 无符号右移 代替 /2 操作，避免 left + right 的超出 int能取的最大值 mid = (left + right) >>> 1; if (target < nums[mid]) { // 如果 目标值 小于 中间值 right = mid - 1; } else if (nums[mid] < target) { // 如果 目标值 大于 中间值 left = mid + 1; } else { // 记录当前中间索引为最大索引 maxIndex = mid; // 缩小左范围，以便能向右查找更大的索引 left = mid + 1; } } return maxIndex; }
