Leetcode刷题详解——在排序数组中查找元素的第一个和最后一个位置

注意事项：找中间元素需要向下取整

因为后续继续移动指针的时候：

左指针：left=mid+1，是会向后移动的，因此区间是会缩小的

右指针：right=mid，可能会原地踏步（比如：如果向上取整的话，如果剩下1，2两个元素的，left==1，right==2，mid==2。更新区间之后，left，right,mid的值没有改变，就会陷入死循环）

4. 寻找有右边界的思路：

1. 用x表示该元素，resLest表示左边界，resRight表示右边界
2. 左边区间（包括右边界）[left,resRight]都是小于等于x的
3. 右边区间[resRight+1,right]都是大于x是的
4. mid的落点情况如下：
   1. 当我们的mid落在[left，resRight]区间的时候，也就是arr[mid]<=target，说明[left,mid-1]（mid不可以舍去，因为有可能是最终结果）都是可以舍去的，此时更新left到mid的位置
   2. 当mid落在[resRight+1,right]的区间的时候，也就是arr[mid]>target，说明[mid,right]内的元素是可以舍去的，此时更新right到mid-1的位置
5. 由此就可以通过二分来快速寻找右边界

注意事项：找中间元素需要向上取整

因为后续继续移动指针的时候：

左指针： left = mid ，可能会原地踏步（⽐如：如果向下取整的话，如果剩下 1,2 两个元
素， left == 1， right == 2，mid == 1 。更新区间之后， left，right，mid 的值
没有改变，就会陷⼊死循环）。
右指针： right = mid - 1 ，是会向前移动的，因此区间是会缩⼩的；
因此⼀定要注意，当right = mid 的时候，要向下取整。

5. 算法流程：

1. 首先判断数组是否为空，如果为空则返回{-1, -1}表示无解。
2. 初始化左指针left为0，右指针right为数组长度减1。
3. 通过二分查找找到目标元素的起始位置。循环条件是左指针left小于右指针right，计算中间位置mid，如果中间位置的元素小于目标元素，则目标元素可能在右半部分，更新左指针left为mid + 1。如果中间位置的元素大于等于目标元素，则目标元素可能在左半部分，更新右指针right为mid。循环结束后，左指针left指向的位置就是目标元素的起始位置。
4. 判断数组中是否存在目标元素，如果左指针left指向的元素不等于目标元素，则不存在目标元素，返回{-1, -1}表示无解。
5. 将目标元素的起始位置保存在变量begin中。
6. 通过二分查找找到目标元素的结束位置。重新初始化左指针left为0，右指针right为数组长度减1。循环条件是左指针left小于右指针right，计算中间位置mid，如果中间位置的元素大于目标元素，则目标元素可能在左半部分，更新右指针right为mid - 1。如果中间位置的元素小于等于目标元素，则目标元素可能在右半部分，更新左指针left为mid。循环结束后，右指针right指向的位置就是目标元素的结束位置。
7. 返回包含起始位置和结束位置的结果数组{begin, right}作为最终答案。

6. C++算法代码：

class Solution {
public:
    vector searchRange(vector& nums, int target) {
        //处理边界情况
        if(nums.size()==0) return {-1,-1};
        int begin=0;
        //二分左端点
        int left=0,right=nums.size()-1;
        while(lefttarget)  right=mid-1;
            else left=mid;
        }
        return {begin,right};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30