LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

题目链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目解析

使用二分查找的方式，分左右端进行查找。首先使用二分找到左端的端点下标，然后在使用二分找到右端的端点下标。

注意事项

求mid注意事项

在使用二分找左端点下标和右端点下标的时候，需要注意的一点是求mid的时候，可能造成死循环的情况，因此我们求左端点的时候mid=left+(right-left)/2;来求，防止就剩两个元素的时候right与mid相等造成死循环，右端点同上只不过mid=left(right-left+1)/2;来防止左端点死循环。

while循环判断条件注意事项

left==right的时候并不能停止循环，因为此时我们还要继续判断，因为我们判断的条件中含有相等这个。

代码(有详细注释)

class Solution
{
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        int n = nums.size();
        // 如果该数组中元素为空 直接返回{-1,-1}
        if (n == 0) return { -1,-1 };
        // 初始化变量
        // begin来记录左端点
        int begin = 0, left = 0, right = n - 1;
        // 先找左端点
        while (left < right)
        {
            // 左边是小于target的 右边是大于等于target的
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target)
                right = mid;
            else
                left = mid + 1;
        }
        if (nums[left] != target)
            return { -1,-1 };
        else
            begin = left;
 
        left = 0;
        right = n - 1;
        while (left < right)
        {
            // 左边是小于等于target的右边是大于target的
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target)
                left = mid;
            else
                right = mid - 1;
        }
        return { begin,right };
    }
};