https://player.bilibili.com/player.html?aid=841423368&bvid=BV1d54y1q7k7&cid=216724849&page=1&high_quality=1
IsBlue()
重点边界条件是left+1<right，这样再执行一次恰好会使得l、r相邻(left<right)。
# 重点l初始值是数组的左边界，r的初始值是数组的右边界.
# 如果二分查找的是数组,l、r的初始值要恰好在数组的范围外
l=-1, r=N # 此处使用数组作为演示，数组的范围是[0,N-1]。所以1=-1,r=N
while l+1 <r: # 只有l+1<r，再执行一次恰好会使得l、r相邻。如果是l<r，这样再执行一次就会编程l=r
m=(l+r)>>1 # (l+r)/2向下取整
if IsBlue(m) # 如果中间值m符合条件
l=m
else:
r=m
# 重点根据题意判断应该返回l还是r
# 为了防止超出边界可以对l或者r进行规范max(0,l)、min(r,N-1)
nums[max(0,l)] nums[min(r,N-1)]
| 任务 | 示例 | 根据上述模板的基本思想如下 |
|---|---|---|
| 目标值是否存在 | 查找目标值 | |
| 74. 搜索二维矩阵 | 第一个大于等于目标值的索引，然后判断第一个值是不是目标值 | |
| 最后一个小于等于目标值的索引，然后判断最后一个是不是目标值 | ||
| 目标值在数组中第一个、最后一个位置 | 第一个错误的版本 | |
| 在排序数组中查找元素的第一个和最后一个位置 | 第一个大于等于目标值的索引 | |
| 最后一个小于等于目标值的索引 | ||
| 要插入的位置 | 搜索插入位置 | 第一个大于等于目标值的位置 |
如果符合有序这一特性的数值二分型题目同样可以使用上述模板。但是数值型不用考虑超出边界的问题。
| 题目 | 范围 | 特性 | 使用上述模板 |
|---|---|---|---|
| 374. 猜数字大小 | [1，n] | 单调递增 | 可以 |
| 367. 有效的完全平方数 | 正整数 | 单调递增 | 可以 |
| x 的平方根 | 非负数 | 单调递增 | 可以 |