銀月の符号

Python 使い見習いの日記・雑記

レシピ追加、バイナリサーチを行う

久しぶりの 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()