アルゴリズム-二分法検索

前提条件:リストは順序付けされ、リストは小さいものから大きいものにする必要があります.
二分法の原理:リストの中間値を見つけて、この値と検索する値の大きさを比較して、この値より大きいならば、区間を左に縮小して、逆に右に縮小します.次に、見つかるまで同じ手順を続けます.
二分法時間複雑度:O(logn)

def bin_search(data,val):
    left = 0
    right = len(data) - 1
    while left <= right:
        mid = (left + right) // 2
        if data[mid] < val:
            left = mid + 1
        elif data[mid] > val:
            right = mid -1
        elif data[mid] == val:
            return mid