Python二分查找的三种思路

二分查找的条件：

1.列表是有序的

2.掐头去尾去中间

第一种（最普通的方式）：

lst = [1, 4, 5, 7, 12, 15, 16, 23, 35, 56] n = 5 left = 0 right = len(lst) - 1 middle = 0 while left <= right:#如果，left==right了，证明左右两边重叠了，如果有这个值，就是left==right时，如果没有那么，直接跳出循环走后面的else就可以了middle = (left + right) // 2if lst[middle] > n:#如果中间值的值，大于想要查找的值，那么想要的值在左侧，所以把右边的right要向左移动。#移动到哪呢？中间值，都比n大，所以移动到middle的左边right=middle-1right = middle - 1elif lst[middle] < n:#中间值小于n，那么n就在右侧，所以向右移动left，移动到哪呢？中间值都小于n,所以left= middle+1left = middle + 1else:print('找到了')break else:print('没有啊')

第二种（递归）：这种方式是，改变列表的长度，所以在使用二分查找时，要知道什么是可以变的，什么是不可以改变的。

''' 遇到问题没人解答？小编创建了一个Python学习交流QQ群：778463939 寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！ ''' def func(n, lst):left = 0right = len(lst) - 1if lst != []:mid = (left + right)//2if n > lst[mid]:func(n, lst[mid+1:]) # 改变列表elif n < lst[mid]:func(n, lst[:mid])# 改变列表else:print("找到了")returnelse:print("没找到")returnn = int(input("请输入你要查找的数:")) func(n, [1,3,5,7,12,36,68,79]) # 78

第三种（递归+函数返回索引）：

def func(n, lst, left, right): # 递归找到什么是可以变的. 什么是不可以变的if left <= right:mid = (left + right) // 2if n > lst[mid]:left = mid + 1return func(n, lst, left, right)elif n < lst[mid]:right = mid - 1return func(n, lst, left, right) # 递归如果有返回值. 所有调用递归的地方必须写returnelse:print("找到了")return mid # 难点else:print("找不到")return -1n = int(input("请输入你要查找的数:")) lst = [1,3,55,98,37,41,2,5,1,4] ret = func(n, lst, 0, len(lst)-1) # 78 print(ret)

说一下，第三种的返回值的问题。因为，调用一次函数，就会在内存中，为这个函数生成一个局部命名空间。返回值，只会返还给调用它的地方，所以需要一层一层的往上返回。这样开始的地方才可以接收到相应的索引。

这也是一种查找对应数字的方式，相对来说，这种方式是比较省时省空间的。

lst = [1, 4, 5, 7, 12, 15, 16, 23, 35, 56，34, 22]#列表无序也没关系 new_lst = [] for i in range(57):#找到列表中最大的值，然后给一个新的列表赋值，而且设置为0new_lst.append(0)for i in lst:#把需要查找的列表中的每个数字当做所以，并且给对应的索引设置的值为1new_lst[i] = 1n = 12 #次数如果比new_lst的长度还大，直接返回，没有这个数就可以了 if new_lst[n] == 1:#把n当做索引取出值，看看里面的值是不是等于1，等于1时，证明n在这个列表里，否则就不在这个列表里print('在呢') else:print('不在')

总结

以上是生活随笔为你收集整理的Python二分查找的三种思路的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。