動機

整理一下

1. [first, last)

左右 * 閉開 => 4種

假設長度為4的array，範圍如下

  1. 0 <= x < 4
  2. 0 <= x <= 3
  3. -1 < x <= 3
  4. -1 < x < 4

如果bsearch到最後，左右兩邊重合

  1. 0 <= x < 0
  2. 0 <= x <= -1
  3. -1 < x <= -1
  4. -1 < x < 0

所以我們還是選第一種左閉右開

因此，終止條件是

while i < j:
    pass

2. mid = first + (last - first) // 2

原本算中點是(last + first)//2，但是有可能會加到溢位!!

改成用起點再加上多的部分

記得，中點就是往開去算，故如果變成右閉左開要用 last - (last-first)//2去算

另外注意，這裡是無條件捨去，另外有無條件進位的中點算法，但我還不知道使用上要怎麼選擇，但有遇過因此被婊的時候

3. first = mid + 1, last = mid

參考文中是用歸納法(那個loop invariant與我印象中的loop invariant不一樣，所以先叫他歸納法)去證為什麼是first = mid + 1, last = mid

但這裡用終止條件的來看，為什麼是first = mid + 1, last = mid

我們的終止條件左閉右開，所以之後的first與last都要左閉右開

因為mid看過了不用保留所以first = mid + 1，那last呢? 右邊是開，所以last = mid

等到了搜尋完成，最後的結果會是last == first，所以在最後last的值會連同first被保留，十分有趣。

總結

再一次，去看參考的文章，必看阿!!!

def lower_bound(array, first, last, value):
  # 求非降序范围[first, last)内第一个不小于value的值的位置
  while first < last: # 搜索区间[first, last)不为空
    mid = first + (last - first) // 2 # 防溢出
    if array[mid] < value:
      first = mid + 1
    else:
      last = mid
  return first # last也行，因为[first, last)为空的时候它们重合

Ref

炒讚，快去看