python中二分查找的原理是什么

这篇文章将为大家详细讲解有关python中二分查找的原理是什么，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

python主要应用领域有哪些

1、云计算，典型应用OpenStack。2、WEB前端开发，众多大型网站均为Python开发。3.人工智能应用，基于大数据分析和深度学习而发展出来的人工智能本质上已经无法离开python。4、系统运维工程项目，自动化运维的标配就是python+Django/flask。5、金融理财分析，量化交易，金融分析。6、大数据分析。

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]为空,则查找不成功。该算法被称为二分查找
"""
 
 
def binary_search(alist, item):
    """非递归"""
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        mid = (first + last) // 2
        if alist[mid] == item:
            found = True
        else:
            if item < alist[mid]:
                last = mid - 1
            else:
                first = mid + 1
    return found
 
 
def binary_search_recursion(alist, item):
    if len(alist) > 0:
        mid = len(alist) // 2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            return binary_search_recursion(alist[:mid], item)
        else:
            return binary_search_recursion(alist[mid + 1:], item)
    return False
 
 
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中二分查找的原理是什么”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。