# 二分法查找可以提高效率, 前提条件: 有序序列 # 二分法: 核心思想: 掐头去尾取中间, 一次砍一半. 两种算法: 常规循环, 递归循环(返回值要返回给上一个) # 常规循环 lst = [22, 33, 44, 55, 66, 77, 88, 99, 101, 238, 345, 456, 567, 678, 789] n = 66 left = 0 # 左边界 right = len(lst) - 1 # 右边界 while left <= right: # 边界, 当右边比左边还小的时候退出循环 mid = (left + right)//2 # 必须是整除. 因为索引没有小数 if lst[mid] > n: right = mid - 1 # 不出现在右边界,把右边界变成现在的中间并且向左移一位 if lst[mid] < n: left = mid + 1 # 不出现在左边界,把右边界变成现在的中间并且向右移一位 if lst[mid] == n: print("找到了这个数") break else: print("没有这个数") # 递归循环 lst = [22, 33, 44, 55, 66, 77, 88, 99, 101, 238, 345, 456, 567, 678, 789] def func(n, left, right): if left <= right: mid = (left + right)//2 if n > lst[mid]: # 在右边 left = mid + 1 # 把左边界变成mid,然后右移一位 # 个人理解: 一层一层函数递归进去,但是结果也要一层一层返回回来到第一层 return func(n, left, right) # 递归 递归的入口 if n < lst[mid]: # 在左边 right = mid - 1 # 把右边界mid,然后左移一位 # 深坑. 函数的返回值返回给调用者 return func(n, left, right) # 递归 if n == lst[mid]: print("找到了") return mid # 通过return返回, 终止递归 # return # 通过return返回. 终止递归 else: print("没有这个数") # 递归的出口 return -1 # 1, 索引+ 2, 什么都不返回, None(避免返回None) # 找66, 左边界:0, 右边界是:len(lst) - 1 print(func(63, 0, len(lst)-1))