Python实现二分查找(折半查找)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python实现二分查找(折半查找)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1105字，纯文字阅读大概需要2分钟。

内容图文

我们在学习编程语言或者算法设计的时候，总是绕不过查找算法和排序算法。对于顺序查找和冒泡查找我们应该是最熟悉的了，如果这两个还不会，真的要加把劲儿了。

刚好最近算法老师在讲分治思想，刚好二分查找就是根据分治思想进行设计的。

在有序数组nums中查找一个数字x，顺序查找的方法是将数组nums中的元素一个一个与x进行比较，时间复杂度为$O(n)$O(n)。

二分查找的主要思想是：充分利用数组nums已经排好序的特点，我们取数组nums的中间位置(mid)的元素$n_1$n1?，用$n_1$n1?与目标数字x进行比较，如果$n_1$n1? 等于x，那么直接返回$n_1$n1?的位置mid；如果$n_1$n1?大于x，则说明x如果在数组中的话，一定是在$n_1$n1?的左侧；如果$n_1$n1?小于x，则说明x如果在数组中的话，一定是在$n_1$n1?的右侧。

那我们只要重复上面的步骤就可以找到目标数字x在数组nums中的位置(或不存在nums中)

Python3实现二分查找的代码如下：

#BinarySearch：find the location of the target number
def BinarySearch(nums:list,x:int) -> int:
    '''
        nums: Sorted array from smallest to largest
        x: Target number
    '''
    left,right = 0,len(nums)-1
    while left <= right:
        mid = (left+right)//2
        if nums[mid] == x:
            return mid
        if nums[mid] < x:
            left = mid+1
        else:
            right = mid-1
    return None

路漫漫其修远兮 吾将上下而求索

内容总结

以上是互联网集市为您收集整理的Python实现二分查找(折半查找)全部内容，希望文章能够帮你解决Python实现二分查找(折半查找)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端