<問題> 整数が昇順に整列された大きさN(10)の配列s (data)に整数keyがあるかを判定する。ある場合は、インデックスを示す。なければ、ないとプリントする。

入力：整数key
出力：配列sに整数keyがある場合は、インデックスを出力。ない場合も、その旨、出力

<実行例>

探索キーを入力してください :14
s[0] = 1
s[1] = 3
s[2] = 4
s[3] = 8
s[4] = 13
s[5] = 14
s[6] = 18
s[7] = 20
s[8] = 21
s[9] = 25
14 is found in s[5]

探索キーを入力してください :23
s[0] = 1
s[1] = 3
s[2] = 4
s[3] = 8
s[4] = 13
s[5] = 14
s[6] = 18
s[7] = 20
s[8] = 21
s[9] = 25
The element 23 is not in s

解答例

def binary_search(key, low, high):
    """ 二分探索 再帰版 p.150も参照のこと"""

    if low > high:
        return -1

    mid = (low + high) // 2
    if s[mid] == key:
        return mid
    elif key < s[mid]:
        return binary_search(key, low, mid - 1)
    else:
        return binary_search(key, mid + 1, high)


if __name__ == '__main__':   # このスクリプト自身が呼び出されたときは、 _name_グローバル変数は_main_になって実行
    s = [1,3,4,8,13,14,18,20,21,25];
    x = int(input('探索キーを入力してください :'))

    for index, elm in enumerate(s):  # 添え字と要素を取り出す
        print('s[%d] = %d' % (index, elm))

    i = binary_search(x, 0, len(s) - 1)

    if (i == -1):
        print('The element %d is not in s' % (x))
    else:
        print('%d is found in s[%d]' % (x,i))

STEP 4.6 二分探索 (再帰) (Python)