原理

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基础教程

标签 Python, python二分查找