Binary search with predicate in Python

Python: predicate の二分検索

predicate P がある値を境に真偽が分かれる場合、その境界を調べるのに二分検索を行うことができる。

整数 x について、P(x) が true となる最小のx（上の図ではa）を検索する処理のPythonによる実装例を以下に示す。

def binary_search(predicate, lower_bound, upper_bound, not_found=0):
  """
  Returns the least x for which predicate P(x) is true.
  
  Predicate P must be assumed:
    for all x in ordered set S, P(x) implies P(y) for all y > x
  
  @param predicate: unary function which returns true or false
  @param lower_bound: lower bound on the search
  @param upper_bound: upper bound on the search
  @param not_found: return value when all the predicates are false
  """
  ret = not_found

  while lower_bound < upper_bound:
    mid = lower_bound + (upper_bound - lower_bound) / 2
    if predicate(mid):
      ret = upper_bound = mid
    else:
      lower_bound = mid + 1

  return ret

参考：
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch