非递减——>有序查找——>二分查找！

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

一、问题描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

二、示例说明

1. 输入：nums = [5,7,7,8,8,10]，target = 8，输出：[3,4]。
   • 在给定的数组中，目标值8的开始位置是索引3，结束位置是索引4。
2. 输入：nums = [5,7,7,8,8,10]，target = 6，输出：[-1,-1]。
   • 目标值6不在给定的数组中，所以返回[-1,-1]。
3. 输入：nums = []，target = 0，输出：[-1,-1]。
   • 空数组中不存在任何目标值，返回[-1,-1]。

三、提示信息

1. 0 <= nums.length <= 105：数组的长度范围。
2. -109 <= nums[i] <= 109：数组中的元素取值范围。
3. nums是一个非递减数组。
4. -109 <= target <= 109：目标值的取值范围。

四、解题思路

这道题，很自然会想到先用二分找到一个值，再从这个值往左右搜索扩展，找到整个区间。

1. 首先使用二分查找找到目标值在数组中的一个位置。
2. 然后分别从这个位置向左右两边扩展，找到目标值的开始位置和结束位置。

需要注意，本题要求时间复杂度为$O(logn)$，在极端情况下，比如所有$nums$数值一样时$O(n)$，会超时，
所以正确的解法是分别找左右两个边界，这样可以保证不会超时。
这样的话就很有意思了，我们要找的其实是左右两边第一个等于target的位置。
现在的难点是，我只会一般的二分查找，也就是不断通过收缩，找到第一个（右边的）target。

前面一直对二分查找的边界，开闭区间以及查找到的是左右边界不清楚，所以这里列出几种不同开闭区间的情况的二分查找代码，复习！

三种二分查找的通俗解释：
以下代码来源灵山大佬
一、二分查找函数
1.闭区间写法：

• 想象你在一个排好序的书架上找一本特定厚度的书（目标厚度就是target）。
• 一开始，你把整个书架从最左边（left = 0）到最右边（right = len(nums) - 1）都作为搜索范围，这就像是确定了一个闭区间[left, right]，你知道在这个范围内肯定能找到那本书或者确定它不在这个书架上。
• 在找书的过程中，每次你都找到中间的位置（mid）看看这本书的厚度。如果中间这本书比目标厚度薄（nums[mid] < target），那你就知道目标书肯定在右边，所以你把搜索范围缩小到[mid + 1, right]，也就是把左边的边界left移到mid + 1的位置。如果中间这本书的厚度大于等于目标厚度，那目标书可能在左边或者就是这本，所以你把搜索范围缩小到[left, mid - 1]，把右边的边界right移到mid - 1的位置。
• 一直这样找下去，直到左边的边界超过右边的边界（left > right），这时候left所指的位置就是最小的满足条件（书的厚度大于等于目标厚度）的位置。如果整个书架都没有满足条件的书，那left就会等于书架的长度，表示没有找到。

# lower_bound 返回最小的满足 nums[i] >= target 的 i
# 如果数组为空，或者所有数都 < target，则返回 len(nums)
# 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]

# 闭区间写法
def lower_bound(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    while left <= right:  # 区间不为空
        # 循环不变量：
        # nums[left-1] < target
        # nums[right+1] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right]
        else:
            right = mid - 1  # 范围缩小到 [left, mid-1]
    return left

作者：灵茶山艾府
链接：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/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2. lower_bound2函数（左闭右开区间写法）：

   • 同样是找书，这次你把书架分成左闭右开的区间。一开始左边是left = 0，表示你从第一本书开始看，右边是right = len(nums)，表示你一直看到最后一本书的右边那个虚拟位置，这个区间就是[left, right)。
   • 在找的过程中，如果中间这本书比目标厚度薄，你就把左边边界移到mid + 1，把搜索范围缩小到[mid + 1, right)；如果中间这本书的厚度大于等于目标厚度，你就把右边边界移到mid，把搜索范围缩小到[left, mid)。
   • 最后当左边边界和右边边界碰到一起的时候（left == right），你就找到了目标位置，返回left或right都可以，因为它们此时是同一个位置。

3. lower_bound3函数（开区间写法）：

   • 这次想象你站在书架外面，左边有一个虚拟的位置（left = -1），右边是书架的最后一本书的右边那个虚拟位置（right = len(nums)），这是一个开区间(left, right)。
   • 找书过程和前面类似，如果中间这本书比目标厚度薄，你就把左边的虚拟位置移到mid，把搜索范围缩小到(mid, right)；如果中间这本书的厚度大于等于目标厚度，你就把右边边界移到mid，把搜索范围缩小到(left, mid)。
   • 最后当左边和右边的距离只有一本书的时候（left + 1 == right），你就找到了目标位置，返回right。

二、searchRange函数

1. 这个函数的目的是在一个排好序的书架（数组nums）中找到一本特定的书（目标值target）的出现范围。
   • 首先调用前面的lower_bound函数找到这本书可能出现的第一个位置start。
   • 如果start等于书架的长度或者这个位置的书不是目标书，那就说明书架上没有这本书，直接返回[-1, -1]。
   • 如果找到了这本书的开始位置，那么可以确定结束位置也存在。通过再次调用lower_bound函数找比目标书厚度大一点的书的位置，然后减一就是目标书的结束位置end。
   • 最后返回这本书的出现范围[start, end]。

在这里插入代码片