Algorithm - Python - 平方根もカッコイイ(ソート済みリスト、反復逐次探索区間の長さ、浮動小数点数と浮動小数点算術、連続領域の二分法、離散二分探索)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の7章(平方根もカッコイイ)、練習問題(問題2)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
def bin_search(nums: list, value, interval: int = 0) -> int:
    '''
    >>> bin_search([], 0)
    -1
    >>> bin_search(list(range(10)), 0)
    0
    >>> bin_search(list(range(10)), 9)
    9
    >>> bin_search(list(range(10)), 5)
    5
    >>> bin_search(list(range(10)), 10)
    -1
    >>> bin_search([], 0, 5)
    -1
    >>> bin_search(list(range(10)), 0, 5)
    0
    >>> bin_search(list(range(10)), 9, 5)
    9
    >>> bin_search(list(range(10)), 5, 5)
    5
    >>> bin_search(list(range(10)), 10, 5)
    -1
    '''
    low, high = 0, len(nums) - 1
    while low <= high and (high - low) >= interval:
        mid = (low + high) // 2
        if nums[mid] < value:
            low = mid + 1
        elif value < nums[mid]:
            high = mid - 1
        else:
            return mid
    for i in range(low, high + 1):
        if nums[i] == value:
            return i
    return -1


if __name__ == '__main__':
    import doctest
    doctest.testmod()

入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))

$ ./sample2.py
Trying:
    bin_search([], 0)
Expecting:
    -1
ok
Trying:
    bin_search(list(range(10)), 0)
Expecting:
    0
ok
Trying:
    bin_search(list(range(10)), 9)
Expecting:
    9
ok
Trying:
    bin_search(list(range(10)), 5)
Expecting:
    5
ok
Trying:
    bin_search(list(range(10)), 10)
Expecting:
    -1
ok
Trying:
    bin_search([], 0, 5)
Expecting:
    -1
ok
Trying:
    bin_search(list(range(10)), 0, 5)
Expecting:
    0
ok
Trying:
    bin_search(list(range(10)), 9, 5)
Expecting:
    9
ok
Trying:
    bin_search(list(range(10)), 5, 5)
Expecting:
    5
ok
Trying:
    bin_search(list(range(10)), 10, 5)
Expecting:
    -1
ok
1 items had no tests:
    __main__
1 items passed all tests:
  10 tests in __main__.bin_search
10 tests in 2 items.
10 passed and 0 failed.
Test passed.
$