Python 二分法笔记

算法：最高效解决问题的办法

算法之二分法

需求：有一个按照从小到大顺序排列的数字列表

传统遍历方式

nums = [-3,4,7,10,13,21,43,77,89]
for i in nums:
if i == 10:
print(i)
break
print(i)

打印：
-3
4
7
10
# 找到10的时候才结束，这就是遍历，从左到右查询，这种效率是非常底的，万一我想要查找的值不是10，而是上万呢？难道还要遍历列表一个一个找？这不现实。

二分法算法方式

【前提是值的大小从左到右依次排序】#<==可以使用sort()先进行一个升序

二分法的原理就是先获取到列表中间的值，对比需要查找的值。

如果查找的值比中间值大了，则从中间值开始到左边的值全部切成新列表重新计算。

如果查找的指比中间值小了，则从中间值开始到右边的值全部切成新列表重新计算。

最后计算结果查找的值既不大于中间值也不小于中间值的时候，则证明找到了需要的值。

注意：

如果列表元素长度为奇数时，则取中间的那个值为中间值，如果为偶数时，取中间第一个值或者第二个值都是可以的，比如[1,2,3,4]，取2或者3都是可以当做中间值的。

'''列表'''
nums = [-3,4,7,10,13,21,43,77,89]
'''需要查找的值'''
find_num = 10

'''递归函数形参find_num接收需要查找的值和形参l列表'''
def binary_search(find_num,l):
'''在每一次查找时显示一次l列表内容'''
print(l)
'''将列表长度整除2，得到中间值的索引'''
mid_index=len(l) //2
'''判断需要查找的值大于中间值，则返回True执行以下代码'''
if find_num > l[mid_index]:
'''将l列表从中间值开始往右全部切出来重新赋值给l列表，这里+1的原因是中间值已经不需要比较了，将中间值的索引+1'''
l=l[mid_index+1:]
'''递归函数将需要查找的值和切好的列表重新进入循环'''
binary_search(find_num,l)
'''判断需要查找的值小于中间值，则返回True执行以下代码'''
elif find_num <l[mid_index]:
'''将l列表从中间值开始往左全部切出来重新赋值给l列表，因为顾头不顾尾的原则，不会取到中间值'''
l=l[:mid_index]
'''递归函数将需要查找的值和切好的列表重新进入循环'''
binary_search(find_num,l)
else:
'''最后，如果既不大于也不等于，就说明找到了该值，打印find it'''
print('find it')

'''传入find_num需要查找的值和nums列表'''
binary_search(find_num,nums)


打印：
-3, 4, 7, 10, 13, 21, 43, 77, 89] #《==第一次，全部查找一遍，找到中间值13
[-3, 4, 7, 10] #《==第二次，10小于中间值13，从中间值开始往左全部切出来重新赋值给l
[10] #《==第三次，
find it

进程已结束,退出代码0
######可以看出，每一次都是一半一半的来找，这要比遍历提升了很大的效率。
######过程分析：
1、第一次循环，列表长度为9,9//2=4,中间值索引为4，索引4的值为13，if判断10小于13，则从中间值开始往左全部切出来重新赋值给列表，因为顾头不顾尾，所以列表切成了[-3,4,7,10]
2、第二次循环，列表长度为4，4//2=2，中间值索引为2，索引2的值为7，if判断10大于7，由于切分时中间索引+1，索引变成了3，索引3的值为10，则从10开始往右全部切出来重新赋值给列表，所以列表切成了[10]
3、第三次循环，列表长度为1，1//2=0，中间值索引为0，索引0的值为10，因为中间值本身就是10，又没有其他值了，所以if判断10不大于也不小于，else返回find it

bug优化

如果找的值在列表中不存在就会报错列表索引超出范围。

nums = [-3,4,7,10,13,21,43,77,89]
find_num = 30
def binary_search(find_num,l):
print(l)
mid_index=len(l) //2
if find_num > l[mid_index]:
l=l[mid_index+1:]
binary_search(find_num,l)
elif find_num <l[mid_index]:
l=l[:mid_index]
binary_search(find_num,l)
else:
print('find it')

binary_search(find_num,nums)

打印：
[21, 43, 77, 89]
[21, 43]
[21]
[]
IndexError: list index out of range
######过程分析：
1、第一次循环，列表长度为9，9//2=4，中间值索引为4，索引的值为13，if判断30大于13，由于切分时中间索引+1，索引变成了5，索引5的值为21，则从21开始往右全部切出来重新赋值给列表，所以列表切成了[21,43,77,89]
2、第二次循环，列表长度为4，4//2=2，中间值索引为2，索引的值为77，if判断30小于77，则从中间值开始往左全部切出来重新赋值给列表，因为顾头不顾尾，所以列表切成了[21,43]
3、第三次循环，列表长度为2，2//2=1，中间值索引为1，索引的值为43，if判断30小于43，则从中间值开始往左全部切出来重新赋值给列表，因为顾头不顾尾，所以列表切成了[21]
4、第四次循环，列表长度为1，1//2=0，中间值索引为0，索引的值为21，if判断30大于21，由于切分时中间索引+1，所以变成了1，索引1的值为空，则从空开始往右全部切出来重新赋值给列表，所以列表切成了[]
#很明显，切出来空就已经有问题了，0已经没有意义了，用索引0去值得时候就会报错超出索引范围了。



# 解决方法：
nums = [-3,4,7,10,13,21,43,77,89]
find_num = 30
def binary_search(find_num,l):
print(l)
if len(l) == 0: #《==加上if判断，如果列表长度为0时则打印找的值不存在并return退出函数递归循环。
print('找的值不存在')
return
mid_index=len(l) //2
if find_num > l[mid_index]:
l=l[mid_index+1:]
binary_search(find_num,l)
elif find_num <l[mid_index]:
l=l[:mid_index]
binary_search(find_num,l)
else:
print('find it')

binary_search(find_num,nums)

打印：
[-3, 4, 7, 10, 13, 21, 43, 77, 89]
[21, 43, 77, 89]
[21, 43]
[21]
[]
找的值不存在

#加油！！！！！！！！