原视频链接：二分查找 红蓝染色法【基础算法精讲 04】，博主：灵茶山艾府

学算法的第四天！昨天因为学视频的时间太晚了，图书馆闭馆，没来得及整理博客，所以迟到一天。今天看的是二分查找，只有一个题目，但是灵茶山艾府老师讲的很细，把左闭右开、左闭右闭等情况都讲了，但是我比较喜欢左闭右开的方式，所以下面的笔记就只整理了左闭右开的方式。

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

1. lower_bound部分思路讲解

下面是题解代码，上面部分的lower_bound函数的目的是“找到第一个大于等于target的元素的索引”，也就是本题真正用到二分查找的地方。

对while循环的符号判断：由于是左闭右开，即[left, right)，所以left和right不可能取到等号，设想一下left和right都等于1，那么就得到一个[1, 1)的区间，显然这个区间无法成立。而如果题目用的是左闭右闭的思路来解的，那么就要用<=。

后面代码的符号判断：同样的，按照左闭右开区间的思路，当列表中间的值小于target，那么所有>=target的值一定在mid的右侧，因此，left的值取mid+1（left如果等于mid，就会包含住小于target的mid值）；

而进入else判断后，也就是列表中间值大于等于target的情况下，说明mid可能是答案，答案在mid左边，也可能让right = mid。注意：虽然[left, mid)不包含mid，但是mid已经检查是满足条件的，我们允许后面搜索排除它，因为如果左边没有更小的满足条件的位置，最终left会收敛到mid。

2. 主程序代码思路讲解

这里丢一个列表，方便理思路：nums = [5,7,7,8,8,10]， target = 8

始终要记住lower_bound函数的目的是“找到第一个大于等于target的元素的索引”。

我们题目的目的是“在排序数组中查找元素的第一个和最后一个位置”。

start调用了lower_bound函数，并找到了“第一个大于等于target的元素的索引”，也就是第一个“8”所在的位置；

找到后进行判断，如果没有找到target就返回[-1, -1];

最后用end再次调用lower_bound函数，找到“第一个大于等于target + 1的元素的索引”，也就是最上面的列表中“10“所在的位置”，得到结果后-1，就能返回正确的结果。

def lower_bound(nums: List[int], target: int) -> List[int]:
    """找到第一个大于等于 target 的元素的索引"""
    # 左闭右开的写法
    left = 0
    right = len(nums) # [left, right)
    while left < right: # 因为左闭右开，如果left = right的话，左闭右开不成立
        # 解决溢出的方案：left + (right - left) // 2
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1 # [mid+1, right)
        else:
            right = mid # [left, mid)
    return left

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 时间复杂度O(log n)
        # 空间复杂度O(1)
        start = lower_bound(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        # 由于数组有序，最后一个等于 target 的位置，就是第一个大于 target 的位置的前一个索引。
        # 而第一个大于 target 的位置，等价于第一个 ≥ target+1 的位置.
        # 因此再次调用 lower_bound(nums, target+1) 得到该索引，再减 1 即可。
        end = lower_bound(nums, target + 1) - 1
        return [start, end]