随笔

今天看了一天数据结构与算法。晚上突然不想学习了，也就没学，休息一下。数据结构看到80多集，3天就看了1/5，感觉还是可以的。加油。所以今天也不想写啥和学习相关的了，就写个二分查找吧。
昨天得知软件GPA3.5就能保研，难受了。诶，不过和我没啥关系，我还是好好学我自己的吧。冲冲冲！

二分查找

Knuth以及很多大佬都说过，二分查找细节极其恶心的。看这篇知乎就完事了。讲的很好。

二分查找有几种写法？它们的区别是什么？ - Jason Li的回答 - 知乎 https://www.zhihu.com/question/36132386/answer/530313852

# [lo, hi)
def lower_bound(array, lo, hi, value):
  while lo < hi:
    mid = lo + (hi - lo) / 2
    if array[mid] < value: lo = mid + 1
    else: hi = mid
  return lo

简单说lo左边的都是小于value的，hi及hi右边的都是大于等于value的，将[lo, hi)区间不断缩小到空时，就到了第一个大于等于value的值。

比起

mid < value ...
mid > value ...
mid == value ...

上述这个lo和hi的语义和之前不太一样。这个lo和hi的语义是要找的value的rank在[lo,hi]里。这个方法还有一个问题是转入左区间需要一次比较，转入右区间有两个比较。这种不均横导致性能不是最优。可以证明在黄金分割点取mid是最优的。
而之前的那个标程就没有这样的问题。它的语义也不一样，value并不一定在[lo, hi)中。只能说value下标一定是大于等于lo的，但是和hi的关系就不好说了，只能说都有可能。
两种方法，虽然语义不同，但是总的来说lo是一直在逼近最终目标的，hi用来缩小区间，锁定lo的上界。
不知道说明白了没，关于这个语义我还要再想想。因为标程用传统的想法，是把[lo, hi)区间分为了[lo, mid) 和 [mid+1, hi)两个区间，好像是少了一个mid。但其实并没有少，因为语义不一样，这个语义的解释我还需要想想。
有几个小tips：

1. 都用<。<自然符合数组中的位置关系，而且对复杂的类也只需要重载<就行。其他关系都用<来模拟。说个最复杂的，x = y <=> !(x<y) && !(y<x)。
2. lower_bound 是x大于等于value的下界。将条件中的<换成<=即成x>value的下界（upper bound）。[lower, upper)就是等于区间。
   对应的，lower-1就是x<value的上界, upper-1就是x<= value的上界。
3. 该算法不存在时返回hi，hi是原区间外第一个位置，最自然表示不存在意义的位置，无需特殊处理。

今天到这里了，睡了。如果有人看到这里……算了，也没人看的。