【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个不降序数组和一个目标值 target，求数组中这个 target 值的下标区间，若无则返回{-1，-1}。

思路分享

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solutions/1980196/er-fen-cha-zhao-zong-shi-xie-bu-dui-yi-g-t9l9/

• 二分查找的开始，虽然算法早就学过，但灵神的讲解十分透彻，十分值得学习。

• 下面的二分，都以如果中间量小于目标量左指针动，否则右指针动的情况，这样会求得二分值的最左处。

• 二分的灵魂在于循环不变量，即在循环中不变的东西，比如，左右指针的区间含义是闭区间，左闭右开，亦或开区间就很重要；还有循环结束后左右指针的位置也是，拿左闭右开举例，结束后，左右指针都处于target值最左处下标，因为左指针保持了 left-1 处必定小于 target，而右指针则保持了 right 处必定大于等于 target。

• 此外要记得溢出的处理问题，除 python 外，求二分的中间下标如果用(left+right)/2的写法可能会溢出，所以要改写为left+(right-left)/2这样就减少了大于阈值的可能。

• 那么目标值的右侧下标怎么求呢？回顾上面左指针的定义，可以保持 left-1 处必定小于 target，那么如果求得 target+1 的左指针位置，那么该位置减一就是 target 的右边界嘛。即使 target+1 这个值不存在，也不妨碍找到这个位置。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    int lowerBound(vector<int> &nums, int target) {
        int left = 0, right = nums.size();
        int middle = 0;
        while(left < right) {
            middle = left +(right-left)/2; // 除python外，防溢出的写法
            if (nums[middle]<target) {
                left = middle+1;
            }
            else {
                right = middle;
            }
        }
        //cout << left << endl;
        return left;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.size() || nums[start] != target) return {-1, -1};
        int end = lowerBound(nums, target+1)-1;
        return {start, end};
    }
};