二分查找有两种实现：通过递归或循环

二分查找的前提是先要保证数组有序

递归

def binarySearch_recursion(sample, value, low, high):
    '''通过递归实现二分法: 返回value的索引'''

    if low > high: # low == high 时，只剩下一个元素
        return None

    mid = low + (high - low) // 2

    if value == sample[mid]:
        return mid
    elif value < sample[mid]:
        return binarySearch_recursion(sample, value, low, mid - 1)
    elif value > sample[mid]:
        return binarySearch_recursion(sample, value, mid + 1, high)

循环

def binarySearch_loop(sample, value):
    low = 0
    high = len(sample) -1

    while True:
        if low > high:
            return None

        mid = low + (high - low) // 2

        if value == sample[mid]:
            return mid
        elif value < sample[mid]:
            high = mid - 1
        elif value > sample[mid]:
            low = mid + 1

github 完整代码 -- binarySearch.py