二分查找
以查找数组有无指定元素为例
模板一
Intro
错位终止 左闭右闭
循环终止时 r = l - 1
更新时 l = c + 1, r = c - 1 实现错位
初始时左闭右闭
返回时通过 l 左侧和 r 右侧的「循环不变」关系，确定while终止后的目标下标。
在「一般」情形中，要考虑 不更新导致的越界 时的返回值
相等或不等的情形都可以用「四种情形」版本，但相等情形应当用「相等返回」版
本，能够在找到相等元素时立即返回结果，一般版本则一定会穷尽二分过程。
① 相等返回
循环不变关系：
对于 #1 行，若进入该分支，则 l 下标更新后其左侧元素必小于target。
对于 #2 行，若进入该分支，则 r 下标更新后其右侧元素必大于target。
while终止时，r 与 l 相邻，r 在 l 左侧一位。对于更新后任意时刻的 l，其左侧元素必不存在
target，对于更新后任意时刻的 r，其右侧元素必不存在target。而while终止时 r 的右侧和 l
的左侧 正好覆盖了所有nums的元素，故此时不存在target，返回-1.
剩余14页未读，继续阅读
资源评论
