（今回は、資料4. 図3のデータを使います。リストで表現すると、長さは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(s, key):
    low = 0
    high = len(s) - 1

    while low <= high:
        mid = (low + high) // 2
        if s[mid] == key:
            return mid

        if s[mid] > key:
            high = mid - 1
        else:
            low = mid + 1

    return -1

s = [1,3,4,8,13,14,18,20,21,25]
x = int(input('探索キーを入力してください :'))  # 文字列をintに

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

i = binary_search(s, x)

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

import bisect

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

print('%d will be inserted in s[%d]' %  (x, bisect.bisect(s, x)))

STEP 2.2 (二分探索）(python)