レシピ追加、バイナリサーチを行う
久しぶりの Python レシピ追加、『112:バイナリサーチを行う』。 bisect 組み込みモジュールを使うだけ。
未執筆かつ簡単そうなものを探してみたら、これが見つかったのでリハビリがてら。
アルゴリズムの勉強のために一から組みたい人は「Python 二分探索」あたりで検索したり、 bisect.py のコードを読むと吉。
# coding: utf-8 u"""二分探索を行う """ from bisect import bisect_left, bisect_right def bsearch_first(seq, value): u"""最初に見つかった index を返す。見つからなければ None を返す >>> L = [1, 2, 3, 3, 3, 4, 6] >>> bsearch_first(L, 1) 0 >>> bsearch_first(L, 3) 2 >>> bsearch_first(L, 5) >>> bsearch_first(L, 0) >>> bsearch_first(L, 7) """ index = bisect_left(seq, value) if index >= len(seq) or seq[index] != value: return None return index def bsearch_last(seq, value): u"""最後に見つかった index を返す。見つからなければ None を返す >>> L = [1, 2, 3, 3, 3, 4, 6] >>> bsearch_last(L, 1) 0 >>> bsearch_last(L, 3) 4 >>> bsearch_last(L, 5) >>> bsearch_last(L, 0) >>> bsearch_last(L, 7) """ index = bisect_right(seq, value) - 1 if index < 0 or seq[index] != value: return None return index def test(): import doctest doctest.testmod() if __name__ == '__main__': test()