python二分查找的原理-图灵python

原理

1、假设表中的元素按升序排列，将表中记录的关键字与检索关键字进行比较，如果两者相等，则检索成功。

2、否则，使用中间位置记录将表分为前后两个子表。

如果中间位置记录的关键字大于搜索关键字，则进一步搜索前子表，否则进一步搜索后子表。重复上述过程，找到合格的记录，使检索成功，或在子表不存在之前。

实例

"""
应用前提：在含有n个元素的有序列中定位目标值的时间复杂性：O(logn)
该算法保持两个参数的低和高，使所有候选条目的索引都位于低和高之间。首先,low=0和high=n-1。然后我们比较目标值和中间值候选项，即索引项[mid]的数据。
mid=L(low+high)考虑以下三种情况：/2：
-假如目标值等于[mid]数据，然后找到正在寻找的值，然后找到成功并终止。
-如果目标值<[mid]数据，重复这个过程的前半部分序列，即索引范围从低到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]
print(ret)

ret=binary_search(17、20、26、31、44、54、55、65、77、69)
print(ret)

以上是python二分搜索的原理，希望对大家有所帮助。更多Python学习指导：python基础教程

本文教程操作环境：windows7系统Python 3.9.1，DELL G3电脑。