请选择 进入手机版 | 继续访问电脑版
楼主: python爱好者
1393 1

[程序分享] 跟黄哥学python序列文章之python二分查找算法 [推广有奖]

  • 1关注
  • 7粉丝

博士生

29%

还不是VIP/贵宾

-

威望
0
论坛币
0 个
通用积分
0
学术水平
21 点
热心指数
30 点
信用等级
13 点
经验
3073 点
帖子
291
精华
0
在线时间
186 小时
注册时间
2013-4-9
最后登录
2020-9-3

python爱好者 发表于 2016-4-5 06:37:17 |显示全部楼层

+2 论坛币
k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群
赵安豆老师微信:zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

感谢您参与论坛问题回答

经管之家送您两个论坛币!

+2 论坛币
#跟黄哥学python序列文章之python二分查找算法

在计算机科学中,二分查找算法(binary search)、也称折半搜索(英语:half-interval search),  
二分搜索法、二分搜索、二分探索,是一种在有序数组中查找某一特定元素的搜索算法。  
搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;  
如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,  
而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。  
这种搜索算法每一次比较都使搜索范围缩小一半。  (来源于维基百科)

# 二分查找循环版  

                #! /usr/bin/python
                # coding:utf-8


                def binary_search_while(key, arr):
                    '''list 必须是排序好的
                    黄哥python培训_python编程思路之四 咨询qq:1465376564
                    http://www.tudou.com/programs/view/Z4IClY5Wj-g/
                    运维如何通过学习python学会编程
                    https://github.com/pythonpeixun/article/blob/master/python/how_to_learn_python.md[/url]
                    黄哥python远程视频培训班
                    https://github.com/pythonpeixun/article/blob/master/index.md[/url]
                    黄哥python培训试看视频播放地址
                    https://github.com/pythonpeixun/article/blob/master/python_shiping.md[/url]
                    '''
                    start = 0
                    end = len(arr) - 1
                    while start <= end:
                            mid = start + (end - start) // 2
                            if arr[mid] < key:
                                    start = mid + 1
                            elif arr[mid] > key:
                                    end = mid - 1
                            else:
                                    return mid
                    return -1

                if __name__ == '__main__':
                    arr = [3, 9, 28, 67, 12, 45]
                    arr.sort()
                    print(binary_search_while(12, arr))
                    print(binary_search_while(3, arr))
                    print(binary_search_while(9, arr))
                    print(binary_search_while(99, arr))



#二分查找递归版  

                #! /usr/bin/python
                # coding:utf-8


                def binary_search_recursion(key, arr, start, end):
                    '''list 必须是排序好的
                    黄哥python培训_python编程思路之四 咨询qq:1465376564
                    http://www.tudou.com/programs/view/Z4IClY5Wj-g/
                    运维如何通过学习python学会编程
                    [url]https://github.com/pythonpeixun/article/blob/master/python/how_to_learn_python.md
                    黄哥python远程视频培训班
                    [url]https://github.com/pythonpeixun/article/blob/master/index.md
                    黄哥python培训试看视频播放地址
                    [url]https://github.com/pythonpeixun/article/blob/master/python_shiping.md
                    '''
                    if start > end:
                        return -1
                    mid = start + (end - start) // 2
                    if arr[mid] > key:
                            return binary_search_recursion(key, arr, start, mid - 1)
                    if arr[mid] < key:
                            return binary_search_recursion(key, arr, mid + 1, end)
                    return mid


                if __name__ == '__main__':
                    arr = [3, 9, 28, 67, 12, 45]
                    arr.sort()
                    print(binary_search_recursion(12, arr, 0, len(arr)-1))
                    print(binary_search_recursion(3, arr, 0, len(arr)-1))
                    print(binary_search_recursion(9, arr, 0, len(arr)-1))
                    print(binary_search_recursion(99, arr, 0, len(arr)-1))


#用途实例:
白名单过滤,有一家商业银行,将数千万客户名单保存为文本文件中,为白名单。  
白名单处理成排序好的数组。可以用二分查找算法快速排除用户账号是不是银行的客户。

[点击黄哥python培训试看视频播放地址](https://github.com/pythonpeixun/article/blob/master/python_shiping.md)

[黄哥python远程视频培训班](https://github.com/pythonpeixun/article/blob/master/index.md)
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

关键词:python recursion Python培训 Python编程 programs 计算机科学 search python 英语 文章

已有 1 人评分经验 论坛币 收起 理由
三世相思2013 + 20 + 20 精彩帖子

总评分: 经验 + 20  论坛币 + 20   查看全部评分

stata SPSS
python爱好者 发表于 2016-4-6 06:30:02 |显示全部楼层
欢迎看看

使用道具

您需要登录后才可以回帖 登录 | 我要注册

京ICP备16021002-2号 京B2-20170662号 京公网安备 11010802022788号 论坛法律顾问:王进律师 知识产权保护声明   免责及隐私声明

GMT+8, 2021-10-28 12:23