python二分查找的原理
原理
1、假设表中的要素按升序排列,将表中间位置记录的关键词与检索关键词进行比较,如果两者相等,则检索成功。
2、否则,利用中间位置记录将表分为前后两个子表。
如果中间位置记录的关键词大于搜索关键词,则进一步搜索前一个子表,否则进一步搜索后一个子表。重复以上流程,找到符合条件的记录,使检索成功,或者在子表不存在之前,此时检索不成功。
实例
""" 应用前提:在一个含有n个元素的有序序列中定位目标值时间复杂度:O(logn) 该算法维持两个参数low和high,这样可使所有候选条目的索引位于low和high之间。首先,low=0和high=n-1。然后我们比较目标值和中间值候选项,即索引项[mid]的数据。 mid=L(low+high)/2]考虑以下三种情况: -如果目标值等于[mid]的数据,然后找到正在寻找的值,则查找成功并且终止。 -如果目标值<[mid]的数据,对前半部分序列重复这一过程,即索引的范围从low到mid-1. -如果目标值>[mid]的数据,对后半部分序列重复这一过程,即索的范围从mid+1到high。 -如果low>high,说明索引范围[low,high]为空,则查找不成功。该算法被称为二分查找 """ defbinary_search(alist,item): """非递归""" first=0 last=len(alist)-1 found=False whilefirst<=lastandnotfound: mid=(first+last)//2 ifalist[mid]==item: found=True else: ifitem<alist[mid]: last=mid-1 else: first=mid+1 returnfound defbinary_search_recursion(alist,item): iflen(alist)>0: mid=len(alist)//2 ifalist[mid]==item: returnTrue elifitem<alist[mid]: returnbinary_search_recursion(alist[:mid],item) else: returnbinary_search_recursion(alist[mid+1:],item) returnFalse if__name__=='__main__': ret=binary_search_recursion([17,20,26,31,44,54,55,65,77,69],26) print(ret) ret=binary_search([17,20,26,31,44,54,55,65,77,69],68) print(ret)
以上就是python二分查找的原理,希望对大家有所帮助。更多python学习指路:python基础教程
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。