Python 2分探索とその派生

はじめに

最近、再帰関数に関する記事を書きました。
特に使うつもりもなく勉強のためだったのですが、効率の良い探索が必要になりました。
丁度、公開した2分探索のを改良すればよかったので助かりました。
せっかくなので改良した関数も役に立つこともあるだろうと公開してみます。
(もっとも実際に使っているのは、PythonではなくてJavascriptでかつ違った実装になっていますが)

n を見つける

python

def binarySearchL(lt, n):
  l, r = 0, len(lt) - 1
  while l <= r:
    middleIndex = int(l + (r - l) / 2)
    middleValue = lt[middleIndex]
    if middleValue > n:
      l, r = l, middleIndex - 1
    elif middleValue < n:
      l, r = middleIndex + 1, r
    else:
      return middleIndex
  return -1

nより大きい最小のものを見つける

python

def binarySearchGt(lt, n):
  l, r = 0, len(lt) - 1
  while l <= r:
    middleIndex = math.floor(l + (r - l) / 2)  # 切り捨て
    middleValue = lt[middleIndex]
    if middleValue > n and r - l > 1:
      l, r = l, middleIndex
    elif middleValue <= n:
      l, r = middleIndex + 1, r
    else:
      return middleIndex
  return -1

nより小さい最大のものを見つける

python

def binarySearchLt(lt, n):
  l, r = 0, len(lt) - 1
  while l <= r:
    middleIndex = math.ceil(l + (r - l) / 2)  # 切り上げ
    middleValue = lt[middleIndex]
    if middleValue >= n:
      l, r = l, middleIndex - 1
    elif middleValue < n and r - l > 1:
      l, r = middleIndex, r
    else:
      return middleIndex
  return -1