Python 3 で数学を。

Python 3 とライブラリで数学の問題を解いていきます。統計学や機械学習はときどき。

アルゴリズム。二分探索。 Binary Search (Python 3)

使用するライブラリ

なし。

Python 3 コード

binary_search.py

#!/usr/bin/env python3


"""(docstring)
"""


def binary_search(data, num):
    """(docstring)
    """
    head = 0
    tail = len(data) - 1

    while head <= tail:
        center = (head + tail) // 2
        if data[center] == num:
            print('{0}{1} {2}{3}'.format(center, ' 番目の要素が一致しました。', '数値: ', num))
            break
        elif data[center] < num:
            head = center + 1
        else:
            tail = center - 1
    else:
        print('見つかりませんでした。')


if __name__ == '__main__':
    import random

    print('動作確認:')
    data = [11, 13, 17, 19, 23, 29, 31]
    num = 17
    binary_search(data, num)
    print('')

    # 数値を変えて繰り返しチェックするのが面倒なので、安直な自動化。
    #
    # 元データとして、random.sample() で重複のない乱数を、0 ~ 19 までの範囲で 7 個作成する。
    # 探す数値として、random.randint() で 0 ~ 10までの範囲で 1 個作成する。
    # binary_search() 内で、元データを sorted() で昇順にソートし、関数呼び出し。
    # それをforで 10 回繰り返す。
    for _ in range(0, 11):
        random_data = random.sample(range(20), 7)
        random_num = random.randint(0, 10)
        binary_search(sorted(random_data), random_num)

出力例

$ python3 binary_search.py
動作確認:
2 番目の要素が一致しました。 数値: 17

0 番目の要素が一致しました。 数値: 0
3 番目の要素が一致しました。 数値: 5
見つかりませんでした。
2 番目の要素が一致しました。 数値: 10
見つかりませんでした。
見つかりませんでした。
見つかりませんでした。
見つかりませんでした。
2 番目の要素が一致しました。 数値: 8
3 番目の要素が一致しました。 数値: 9
2 番目の要素が一致しました。 数値: 2

参考文献

アルゴリズム初心者向けでは秀逸:

アルゴリズムを、はじめよう

アルゴリズムを、はじめよう

広告を非表示にする