力扣热门100题之在排序数组中查找元素的第一个和最后一个位置

思路

1. 先用二分找第一个等于 target的位置（左边界）
2. 再用二分找最后一个等于 target的位置（右边界）
3. 没找到就返回[-1,-1]

• 左边界：遇到>= target就往左缩，最终l停在第一个目标位置
• 右边界：遇到<= target就往右扩，最终r停在最后一个目标位置
• 最后判断一下是否真的等于 target，不是就返回 -1

完整代码实现

class Solution { public int[] searchRange(int[] nums, int target) { int left = findLeft(nums, target); int right = findRight(nums, target); return new int[] { left, right }; } public int findLeft(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; } } // 找到的位置必须合法且等于 target if (l < nums.length && nums[l] == target) return l; return -1; } public int findRight(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] <= target) { l = mid + 1; } else { r = mid - 1; } } if (r >= 0 && nums[r] == target) return r; return -1; } }