112:バイナリサーチを行う

バイナリサーチを行うには bisect モジュールを用いて作成した次の関数を使います。 使用法はコードの docstring を参照してください。

# 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()