python二分查找算法的三种实现方法

二分查找. 每次能够排除掉⼀半的数据. 查找的效率非常⾼. 但是局限性比较⼤. 必须是有
序序列才可以使⽤⼆分查找

• 要求: 查找的序列必须是有序序列

(1) 使用基本的算法实现：

lst = [4, 56, 178, 253, 625, 1475, 2580, 3574, 15963]

n = int(input(\"请输入一个数字n:\"))      # 56

left = 0                              # 左边界
right = len(lst) - 1                  # 末尾的索引  右边界
while left <= right:                  # 当左边界大于右边界结束循环

    mid = (left + right) // 2         # 求中间的索引坐标
    if n < lst[mid]:                  # 判断你的数字和中间数的大小比较 .
        right = mid - 1               #  右边界往左移动

    elif n > lst[mid]:
        left = mid + 1                # 左边界往右移动

    else:
        print(\"找到了\")               # 找到了目标数字
        break
else:                                 # 当左比右大, 循环结束. 没有找到目标数
    print(\"没找到\")

（2）使用递归实现：

lst = [4, 56, 178, 253, 625, 1475, 2580, 3574, 15963]

def binary_search(lst, n, left, right):
    if left > right:
        return False
    mid = (left + right) // 2
    if n > lst[mid]:
        left = mid + 1
        # 当递归有返回值的时候. 需要写return. 否则有可能接收不到返回值
        return binary_search(lst, n, left, right)
    elif n < lst[mid]:
        right = mid - 1
        return binary_search(lst, n, left, right)
    else:
        print(\"找到了\")
        return True

n = int(input(\"请输入一个数字n:\")) # 178
ret = binary_search(lst, n, 0, len(lst)-1)
print(ret)

# 结果：
# 请输入一个数字n:178
# 找到了
# True

切记：当递归有返回值的时候. 需要写return. 否则有可能接收不到返回值

（3）对列表切片：

def binary_search(lst, n):
    if len(lst) == 0:
        return False
    left = 0
    right = len(lst) - 1
    mid = (left + right) // 2
    if n > lst[mid]:
        left = mid + 1
        # 当递归有返回值的时候. 需要写return. 否则有可能接收不到返回值
        return binary_search(lst[mid+1:], n)
    elif n < lst[mid]:
        right = mid - 1
        return binary_search(lst[:mid], n)
    else:
        print(\"找到了\")
        return True