在分而治之的方法中,将手头的问题分成较小的子问题,然后分别解决每个问题,当无涯教程继续将子问题划分为更小的子问题时,最终可能会达到无法再进行划分的阶段。那些原子的最小可能的子问题得以解决,最后合并所有子问题的解决方案,以获得原始问题的解决方案。
在二分搜索中,获取元素的排序列表,然后开始在列表中间寻找元素,如果搜索值匹配 使用列表中的中间值完成了搜索,否则,通过选择是否继续将一半列表的右半部分或左半部分,取决于搜索元素的值,由于列表已排序,因此这比线性搜索要快得多。
def bsearch(list, val): list_size=len(list) - 1 idx0=0 idxn=list_size # 找到中间的最大值 while idx0 <= idxn: midval=(idx0 + idxn)//2 if list[midval] == val: return midval # 比较中间最值的值 if val > list[midval]: idx0=midval + 1 else: idxn=midval - 1 if idx0 > idxn: return None # 初始化排序列表 list=[2,7,19,34,53,72] # 打印搜索结果 print(bsearch(list,72)) print(bsearch(list,11))
执行以上代码后,将产生以下输出:
5 None
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)