LeetCode 34：在排序数组中查找元素的第一个和最后一个位置（含思维过程）

题目链接：LeetCode 34 - Find First and Last Position of Element in Sorted Array。leetcode​
题目大意：给定一个按非递减顺序排序的整数数组 nums，和一个目标值 target，要求在数组中找到 target 出现的第一个位置和最后一个位置，返回 [start, end]。如果不存在，返回 [-1, -1]，并且算法时间复杂度必须是 O(log⁡n)O(\log n)O(logn)。leetcode​

最朴素的想法：先找到一个，再往两边扫

一开始的直觉很自然：
先用二分查找找到某个 mid，使得 nums[mid] == target。
从 mid 向左扫，直到遇到第一个不等于 target 的位置，前一个就是 start。
从 mid 向右扫，直到遇到第一个不等于 target 的位置，前一个就是 end。
这个思路在正确性上没问题，但有一个明显的问题：
在极端情况下，比如 nums = [8,8,8,8,8,8]，虽然找到一个 8 用了 O(log⁡n)O(\log n)O(logn)，但是向左、向右的线性扫描又回到了 O(n)O(n)O(n)。
综合起来，最坏复杂度是 O(n)O(n)O(n)，不满足题目要求的 O(log⁡n)O(\log n)O(logn)。
所以，向两边"线性扫"是不行的，必须连"找左右边界"这一步也用二分来做。

改进方向：用二分专门找"边界"

既然数组有序，而且要 O(log⁡n)O(\log n)O(logn)，自然想到：
不仅要用二分找一个 target，
还要用"改造过的二分"去分别找最左和最右的 target。
这里有两个关键的小问题：
找左边界时，nums[mid] == target 时怎么办？
不能直接返回，因为左边可能还有 target。
正确做法是：记录当前 mid 是一个候选答案，然后把 right 收缩到 mid - 1，继续往左找。
找右边界是不是对称的？
是的，找右边界时，nums[mid] == target 时，记录答案，然后把 left 收缩到 mid + 1，继续往右找。
所以，思路变成：
写一个 find_start_position：
尽量往左压缩，找到"第一个等于 target 的位置"。
写一个 find_end_position：
尽量往右压缩，找到"最后一个等于 target 的位置"。
每个函数内部都是一次完整的二分，整体只做了常数次二分，复杂度是 2⋅log⁡n2 \cdot \log n2⋅logn，在大 O 记号下仍然是 O(log⁡n)O(\log n)O(logn)，完全符合要求。enjoyalgorithms+1​

关于"2 次二分是不是超了 O(log n)？"

从渐进复杂度的角度，2⋅log⁡n2 \cdot \log n2⋅logn、3⋅log⁡n3 \cdot \log n3⋅logn 等都写作 O(log⁡n)O(\log n)O(logn)，常数因子会被忽略。enjoyalgorithms​
实际上，很多官方题解和主流题解就是 “两次边界二分”：
第一次找左边界；
第二次找右边界；
这一点在面试中是完全没有问题的。

最终实现：两个边界二分函数

下面是用 C 写的完整代码，拆成三个函数：
find_start_position：找左边界。
find_end_position：找右边界。
searchRange：主函数，负责处理空数组、调用两个二分，并返回结果。
代码如下：

intfind_end_position(int*nums,intnumsSize,inttarget){intleft,right,mid,end_position;left=0;right=numsSize-1;end_position=-1;while(left<=right){mid=left+(right-left)/2;if(nums[mid]==target){end_position=mid;left=mid+1;}elseif(nums[mid]<target){left=mid+1;}else{// nums[mid] > targetright=mid-1;}}returnend_position;}intfind_start_position(int*nums,intnumsSize,inttarget){intleft,right,mid,start_position;left=0;right=numsSize-1;start_position=-1;while(left<=right){mid=left+(right-left)/2;if(nums[mid]==target){start_position=mid;right=mid-1;}elseif(nums[mid]<target){left=mid+1;}else{// nums[mid] > targetright=mid-1;}}returnstart_position;}/** * Note: The returned array must be malloced, assume caller calls free(). */int*searchRange(int*nums,intnumsSize,inttarget,int*returnSize){intstart_position,end_position;int*result;result=(int*)malloc(2*sizeof(int));if(!nums||!numsSize){result[0]=-1;result[1]=-1;*returnSize=2;returnresult;}start_position=find_start_position(nums,numsSize,target);end_position=find_end_position(nums,numsSize,target);result[0]=start_position;result[1]=end_position;*returnSize=2;returnresult;}

这份代码在 LeetCode 上可以通过所有用例，实际提交记录：
用例：88 / 88 全部通过。
运行时间：0 ms，击败 100% 提交。
内存使用：9.82 MB。leetcode​

小结：这道题教会了什么？

这道题的关键不在"会不会写二分"，而在于：
能否把"找到一个 target"提升为"找到一段 target 的边界"；
知道 边界二分的典型写法：命中 target 时不要停，而是继续压缩一端；
能清楚解释为什么"两次二分仍然是 O(log⁡n)O(\log n)O(logn)“；
通过自己一步步把"线性往两边扫"的想法改进为"左右边界都用二分”，是一个很典型的"从直觉解到最优解"的思考路径。
如果想把这个模式记牢，可以再去刷几道类似的"找第一次 / 最后一次出现位置"的题，尽量统一成一套"找左边界 / 右边界"的模板，会在面试里非常加分。