Python二分法查找,Python实现二分查找

　　原理

　　1.假设表中的元素按升序排列，将记录在表中间的关键字与搜索关键字进行比较。如果它们相等，则搜索成功。

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

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

　　实例

　　应用前提：在包含n个元素的有序序列中定位目标值的时间复杂度：O(logn)

　　该算法维护两个参数，low和high，以便所有候选条目的索引都在low和high之间。一开始，低=0，高=n-1。然后我们比较目标值和中间值候选的数据，也就是指标项[mid]。

　　Mid=L(低高)/2]考虑以下三种情况3360

　　-如果目标值等于[mid]的数据，然后找到了您要查找的值，则搜索成功并终止。

　　-如果目标值[mid]是数据，对序列的前半部分重复此过程，即索引范围从低到中1。

　　-如果目标值[mid]是数据，对序列的后半部分重复此过程，即电缆的范围是从mid 1到high。

　　-如果lowhigh，索引范围[低，高]为空，则搜索不成功。这种算法被称为二分搜索法。

　　defbinary_search(列表，项目):

　　非递归

　　first=0

　　last=len(list)-1

　　发现=假

　　while first=lastandnotfound :

　　mid=(first last)//2

　　ifalist[mid]==item:

　　发现=真

　　else:

　　ifitemalist[mid]:

　　最后=中间1

　　else:

　　first=mid 1

　　找到returnfound

　　defbinary _ search _ recursion(list，item):

　　iflen(列表)0:

　　mid=len(list)//2

　　ifalist[mid]==item:

　　返回真

　　elifitemalist[mid]:

　　return binary _ search _ recursion(list[: mid]，item)

　　else:

　　return binary _ search _ recursion(list[mid 1:]，item)

　　返回False

　　if__name__==__main__:

　　ret=binary _ search _ recursion([17，20，26，31，44，54，55，65，77，69]，26)

　　打印(ret)

　　ret=binary_search([17，20，26，31，44，54，55，65，77，69]，68)

　　Print(ret)以上是python二分搜索法的原理。希望对你有帮助。更多python学习方向：Python基础课程

　　本教程运行环境：windows7系统，Python 3.9.1，DELL G3电脑。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。