一、迭代

def binary_search(key, ls):
    left = 0
    right = len(ls) -1

    while left <= right:
        mid = (left + right) // 2

        if key == ls[mid]:
            return mid
        elif key < ls[mid]:
            right = mid - 1
        elif key > ls[mid]:
            left = mid + 1
    return -1

二、递归

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