python 、普通二分法查找与递归实现二分法查找

 常规二分法查找：

lst = [11, 22, 33, 44, 55, 66, 77, 88, 99, 123, 234, 345, 456, 567, 678, 789, 1111]
n = 567
left = 0
right = len(lst) - 1
count = 1
while left <= right:
    middle = (left + right) // 2
    if n > lst[middle]:
        left = middle + 1
    elif n < lst[middle]:
        right = middle - 1
    else:
        print('查找了%s次' % count)
        print(middle)
        break
    count += 1
else:
    print('没有')

运行结果：

 递归实现二分法查找：

lst = [11, 22, 33, 44, 55, 66, 77, 88, 99, 123, 234, 345, 456, 567, 678, 789, 1111]


def fun(left, right, n):
    middle = (left + right) // 2
    if left > right:    # 没有这个数需要返回，否则会报错
        return -1
    if n > lst[middle]:
        left = middle + 1
    elif n < lst[middle]:
        right = middle - 1
    else:
        return middle
    return fun(left, right, n)    #这个return必须要加.否则接收到的永远是None.


print(fun(0, len(lst) - 1, 125))

运行结果：