有序数组中找值t
若存在，t一定在范围[l,u]中，x[l]<=t<=x[u]。初始l=0, u=n-1。写起来思路是排除不可能包含t的范围。
有序数组中找第一个出现的值t
变成找第一个>=t的值，看它是不是t。不变式x[l]<t<=x[u]，当l+1=u时x[u]就是第一个>=t的值。 所以主循环是while (l+1 < u) {}，循环结束时x[u]是第一个>=t的值。
要初始化l=-1, u=n。因为循环中l+1<u，实际访问的m=(l+u)/2一定l<m<u，不会访问数组最两端的l和u，可以假想x[l]=-∞、x[n]=∞。见pp p80
l = -1; u = n;
while l + 1 < u
m = (l + u) / 2
if x[m] >= t // 参照不变式x[l]<t<=x[u]的x[u]>=t部分
u = m
else
l = m
// x[u]是第一个>=t的值
p = u
if p >= n || x[p] != t
p = -1
上述不变式思路最清晰。还有另一种写法理解下不用记，关注在排除不可能范围，而不是保持不变式。初始范围l=0, u=n-1，需要循环结束时l和u刚好交错，l=u+1, x[l]>=t, x[u]<t，x[l]是第一个>=t的值。两种写法其实一样，正说反说的区别，把l=l'-1, u=u'+1代入标准式就得下式。
l = 0; u = n - 1;
while l <= u
m = (l + u) / 2
if x[m] >= t
u = m - 1
else
l = m + 1
// x[l]是第一个>=t的值
p = l
if p >= n || x[p] != t
p = -1
见 http://ranger.uta.edu/~weems/NOTES2320/binarySearchRange.c
有时还有种写法知道下不用记，与标准写法比较，看初始时是改了l还是u。比如改了l，就把l相关的都改动，把l=l'-1代入标准式可得。
l = 0; u = n;
while l < u
m = (l + u) / 2
if x[m] >= t
u = m
else
l = m + 1
// x[u]是第一个>=t的值
p = u
if p >= n || x[p] != t
p = -1
综上，l和u两端跟实际区间比，两端开区间是标准写法。哪端闭区间哪端作改动：比如第二种写法，两端闭区间，l和u相关的作改动；第三种写法，前闭后开，l相关的作改动。
为了防止死循环，总是检查2个元素时的执行能将范围减1。如果mid的取值（比如取小的中位数的mid=lo+(hi-lo)/2）和if...else...某分支的取值（比如mid=lo）相同，那就会死循环。
二分搜索本质：在 [0 ... 0 1 1 ...]的数组中找第一个1的位置
比如在有序数组中找第一个>=t的数，cond(x) { x>=t }。u总是满足条件的位置，l总是不满足条件的位置。
l = -1; u = n;
while l + 1 < u
m = (l + u) / 2
if cond(m) // 满足条件
u = m
else
l = m
...
二分搜索常用来找满足条件的最值。先根据题意列出各变量关系，只要表达式是关于某变量x的单调函数expr(x)，就能用二分搜索解。
- 如果expr(x)关于x递增↑，条件式cond(x){ expr(x)>=某常量 }
- 如果expr(x)关于x递减↓，条件式cond(x){ expr(x)<=某常量 }
二分搜索可用在，比如：
- 找最大值的最小值
- 找最小值的最大值
- 找均值的最大值
- 找第k小的数x，表达式count(x){ <=x的个数 }关于x递增，条件式guess(x){ count(x)>=k }
- 找第k大的数x，表达式count(x){ >=x的个数 }关于x递减，条件式guess(x){ count(x)<=k }
有序数组中找最后一个出现的值t
只要找第一个>t的数，然后看它左边的数是不是t。不变式x[l]<=t<x[u]，当l+1=u时x[l]就是最后一个<=t的值。 修改标准的二分搜索写法：1. 条件式由>=变成>，去掉等号，2. 最终要找的为u前面一位的l。