二分法

这里我们对二分法的初始值，循环条件，条件语句进行讨论。

初始值

对于左右两个端点的初始值，在一个长度为 $n$ 的数组上，左经常用到的有两种情况：

左闭右闭，即 $[0, n-1]$
左闭右开，即 $[0, n)$

上述两种初始化对应的中间值计算方式均为

\begin{aligned} m = \lfloor\frac{(r - l)}{2}\rfloor + l. \end{aligned}

循环条件

对于循环条件我们经常见到的也有两种情况：

$l \leq r$ ，对应着 $l > r$ 退出循环
$l < r$ ，对应着 $l =r$ 退出循环

上面两种循环条件各自对应着以下两种更新方式

$l=m+1$ , $r = m -1$
$l=m+1$ , $r = m$

也不难理解，因为 $r$ 为开区间，在第二种更新中并没有取 $m-1$ 。（个人更喜欢第一种循环和更新。）

第一种更新需要注意的特殊场景是，返回的 $l$ 或者 $r$ 可能是超出范围的。例如当target大于所有元素时，判断条件是 $l=m+1$ 是，最终返回的是 $l=n$ 。

条件语句

在各种类似“第一个大于k的坐标”，“小于等于k的最小坐标”等等题目中，if-else判断条件起着重要的作用，例如下面的代码中返回的 $l$ 是大于 target的最小值的坐标。

def f(nums, l, r)
    while l <= r:
        mid = (r - l) // 2 + l
        if nums[mid] <= target:
            l = mid + 1  # 确保更新后左侧的区域，( ,l), 一定小于等于target
        else:
            r = mid -1  # 确保更新后右侧的区域, (r, ), 一定是大于target
    return l