Binary search 模版

note.md

找一個準確值

循環條件: l <= r

縮減搜索空間: l = mid + 1, r = mid - 1

找一個模糊值(比4大的最小數)

循環條件: l < r

縮減搜索空間: l = mid, r = mid - 1 或者 l = mid + 1, r = mid

萬用型

循環條件: l < r - 1

縮減搜索空間: l = mid, r = mid

Template: [l, r)

def binary_search(l, r):
  while l < r:
    m = l + (r - l) / 2
    if f(m): return m # optional
    if g(m):
      r = m # new range [l, m)
    else:
      l = m + 1 # new range [m+1, r)
   return l # or not found