京公网安备11010502063487号给定一个升序数组和一个目标值，返回目标值出现的第一个和最后一个下标；不存在返回 [-1, -1]。要求 O(log n)。这道题的关键是别用"二分找到任意一个，再线性向两边扩展"：整个数组都是目标值时，扩展会退化成 O(n)。正确做法是做两次二分，分别找"第一个大于等于 target 的位置"和"第一个大于等于 target + 1 的位置再往前一格"。本文用真实的步数展示线性扩展在最坏情形下的代价，给出五种语言的实现，并把两次二分做成分步演示。
完整题目见官方页面（链接在文末）。基准解是线性扫描，收集所有等于 target 的下标，取第一个和最后一个。一共 12 组用例，覆盖：官方示例、目标不存在、空数组、单个元素、目标在头或尾、整个数组都是目标：
输入 [[5,7,7,8,8,10],8] 输出 [3,4] 输入 [[5,7,7,8,8,10],6] 输出 [-1,-1] 输入 [[],0] 输出 [-1,-1] 输入 [[1],1] 输出 [0,0] 输入 [[1],2] 输出 [-1,-1] 输入 [[2,2],2] 输出 [0,1]
先二分找到任意一个等于 target 的位置，再向左右两边逐个扩展，看起来也能得到答案，但如果整个数组都是 target，二分第一次就命中，随后要向两边各扩展约一半的长度。下面是数组长度 n 时两种做法真实统计的步数（二分的比较次数，加上扩展的移动次数）：
整个数组都是 target 时的比较/移动次数（数组长度 n）： n= 1000: 二分后线性扩展 1000 步 两次二分 19 步 结果一致=True n= 100000: 二分后线性扩展 100000 步 两次二分 33 步 结果一致=True n= 1000000: 二分后线性扩展 1000000 步 两次二分 39 步 结果一致=True
数组全是 7 时，线性扩展的步数就是 n（1000、100000、1000000），而两次二分只需要 19、33、39 步，随 log n 增长。结果两种做法一致，差别只在耗费的步数。
先写一个通用的 lowerBound(x)：返回第一个大于等于 x 的位置，都比 x 小就返回数组长度。用 [lo, hi) 左闭右开区间，nums[mid] < x 时 lo = mid + 1，否则 hi = mid。第一个位置 first = lowerBound(target)，如果越界或者那里的值不是 target，说明不存在。最后一个位置是 lowerBound(target + 1) - 1：第一个大于 target 的位置，往前一格就是最后一个等于 target 的位置。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def lower_bound(nums, x): # 第一个 >= x 的位置（都比 x 小就返回 len(nums)） lo, hi = 0, len(nums) while lo < hi: mid = (lo + hi) // 2 if nums[mid] < x: lo = mid + 1 else: hi = mid return lo def solve(nums, target): first = lower_bound(nums, target) # 第一个 >= target 的位置 if first == len(nums) or nums[first] != target: return [-1, -1] last = lower_bound(nums, target + 1) - 1 # 第一个 > target 的位置再往前一格 return [first, last]
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[5,7,7,8,8,10],8] → [3,4] [[5,7,7,8,8,10],6] → [-1,-1] [[],0] → [-1,-1] [[1],1] → [0,0] [[1],2] → [-1,-1] [[2,2],2] → [0,1]
Java · 解法代码class Solution { private int lowerBound(int[] nums, int x) { // 第一个 >= x 的位置（都比 x 小就返回 nums.length） int lo = 0, hi = nums.length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < x) lo = mid + 1; else hi = mid; } return lo; } public int[] searchRange(int[] nums, int target) { int first = lowerBound(nums, target); // 第一个 >= target 的位置 if (first == nums.length || nums[first] != target) return new int[]{-1, -1}; int last = lowerBound(nums, target + 1) - 1; // 第一个 > target 的位置再往前一格 return new int[]{first, last}; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[5,7,7,8,8,10],8] → [3,4] [[5,7,7,8,8,10],6] → [-1,-1] [[],0] → [-1,-1] [[1],1] → [0,0] [[1],2] → [-1,-1] [[2,2],2] → [0,1]
Go · 解法代码func lowerBound(nums []int, x int) int { // 第一个 >= x 的位置（都比 x 小就返回 len(nums)） lo, hi := 0, len(nums) for lo < hi { mid := lo + (hi-lo)/2 if nums[mid] < x { lo = mid + 1 } else { hi = mid } } return lo } func searchRange(nums []int, target int) []int { first := lowerBound(nums, target) // 第一个 >= target 的位置 if first == len(nums) || nums[first] != target { return []int{-1, -1} } last := lowerBound(nums, target+1) - 1 // 第一个 > target 的位置再往前一格 return []int{first, last} }
$ go build -o bin . && ./bin < cases.jsonl [[5,7,7,8,8,10],8] → [3,4] [[5,7,7,8,8,10],6] → [-1,-1] [[],0] → [-1,-1] [[1],1] → [0,0] [[1],2] → [-1,-1] [[2,2],2] → [0,1]
JavaScript · 解法代码function lowerBound(nums, x) { // 第一个 >= x 的位置（都比 x 小就返回 nums.length） let lo = 0, hi = nums.length; while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] < x) lo = mid + 1; else hi = mid; } return lo; } function searchRange(nums, target) { const first = lowerBound(nums, target); // 第一个 >= target 的位置 if (first === nums.length || nums[first] !== target) return [-1, -1]; const last = lowerBound(nums, target + 1) - 1; // 第一个 > target 的位置再往前一格 return [first, last]; }
$ node run.js < cases.jsonl [[5,7,7,8,8,10],8] → [3,4] [[5,7,7,8,8,10],6] → [-1,-1] [[],0] → [-1,-1] [[1],1] → [0,0] [[1],2] → [-1,-1] [[2,2],2] → [0,1]
C++ · 解法代码#include <vector> using namespace std; class Solution { int lowerBound(const vector<int>& nums, int x) { // 第一个 >= x 的位置（都比 x 小就返回 nums.size()） int lo = 0, hi = nums.size(); while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < x) lo = mid + 1; else hi = mid; } return lo; } public: vector<int> searchRange(vector<int>& nums, int target) { int first = lowerBound(nums, target); // 第一个 >= target 的位置 if (first == (int)nums.size() || nums[first] != target) return {-1, -1}; int last = lowerBound(nums, target + 1) - 1; // 第一个 > target 的位置再往前一格 return {first, last}; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[5,7,7,8,8,10],8] → [3,4] [[5,7,7,8,8,10],6] → [-1,-1] [[],0] → [-1,-1] [[1],1] → [0,0] [[1],2] → [-1,-1] [[2,2],2] → [0,1]
共 12 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 12/12 Java 通过 12/12 Go 通过 12/12 JavaScript 通过 12/12 C++ 通过 12/12
Python 版本另外和线性扫描做了随机对拍，数组有很多重复值，target 有一定概率不存在：
随机对拍 20000 组（长度 0 到 15、取值 -6 到 6 的有序数组（重复值很多），target 取 -7 到 7（包括不存在的）），solve 与 brute 的结果全部一致。
另外四种语言只在上面 12 组固定用例上验证过，没有做大规模随机对拍。这道题的代价是两次对数级的二分，实测意义主要在上面比较线性扩展的那一节，所以没有再单独做规模对比实验。
下面的演示用官方示例 [5, 7, 7, 8, 8, 10] 和 target = 8。第一次二分找到第一个 ≥ 8 的位置 3；第二次二分找第一个 ≥ 9 的位置 5，往前一格得到最后一个位置 4。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。