文档章节

跟黄哥学python序列文章之python二分查找算法

黄哥Python培训
 黄哥Python培训
发布于 2016/04/05 06:31
字数 869
阅读 345
收藏 5

#跟黄哥学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
	    黄哥python远程视频培训班
	    https://github.com/pythonpeixun/article/blob/master/index.md
	    黄哥python培训试看视频播放地址
	    https://github.com/pythonpeixun/article/blob/master/python_shiping.md
	    '''
	    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学会编程
	    https://github.com/pythonpeixun/article/blob/master/python/how_to_learn_python.md
	    黄哥python远程视频培训班
	    https://github.com/pythonpeixun/article/blob/master/index.md
	    黄哥python培训试看视频播放地址
	    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培训试看视频播放地址

黄哥python远程视频培训班

© 著作权归作者所有

黄哥Python培训
粉丝 39
博文 21
码字总数 14219
作品 0
海淀
私信 提问
排序算法(3) -- 插入排序

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/87967009 一、前言 直接插入排序(...

dby_freedom
02/27
0
0
【python】手把手带你掌握算法基础01_二分法和选择排序法的实现

一、大O表示法 学算法就绕不开大O表示法,大O法可以告诉我们算法的时间和空间复杂度。 我们先聊点简单的,请你从1数到10,这里的复杂度是多少呢?O(10)。那么从1数到n,归纳法告诉我们,复...

徐胥
05/22
0
0
Python数据结构总结篇

数据结构篇主要是阅读[Problem Solving with Python]( http://interactivepython.org/courselib/static/pythonds/index.html)时写下的阅读记录,当然,也结合了部分[算法导论]( http://en.wi...

宅男潇涧
2014/07/06
620
0
python实现lower_bound和upper_bound

由于对于二分法一直都不是很熟悉,这里就用C++中的lowerbound和upperbound练练手。这里用python实现 lowerbound和upperbound本质上用的就是二分法,lowerbound查找有序数组的第一个小于等于目...

mambakb
2018/11/29
0
0
python 二分插入、遍历目录

这两道题是之前面试测试开发遇到的,今天分享给大家。 遍历文件 python 遍历文件夹下所有文件,并打印出所有文件名 二分法 python 在顺序列表中,二分法查找且插入一个数

lvyz0207
2018/05/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CSS3

一.复杂选择器 1.兄弟选择器 具备相同父级元素的平级元素之间称为兄弟元素 注意:兄弟选择器,只能往后,不能往前找 (1).相邻兄弟选择器,获取紧紧挨着某元素后面的兄弟元素 选择器1+选择器2...

wytao1995
12分钟前
1
0
Jmeter录制

1. 加HTTP(s) Test Script Recorder 2. 在 recorder下面加reocrding controller 3. 在HTTP(s) Test Script Recorder中设置下面几项 4. browser设置proxy, 注意端口要和step3中jmeter中的一致......

Rebecca_Hu
16分钟前
3
0
DIV+CSS忽悠前端小白

在大约两年前,DIV+CSS是一对很诱人的组合,会用DIV+CSS制作网页的人,常常会被人赞以大拇指的,记得06年初的时候,我用 div+css布局的一个纯静态网站还拿了学校网页设计比赛的一个奖。 今天...

前端老手
20分钟前
3
0
Win10子系统 linux(Ubuntu18.04) 安装Docker

1)原文件备份 sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak 2)编辑源列表文件 sudo vim /etc/apt/sources.list 3)将原来的列表删除,添加如下内容(中科大镜像源) deb http...

jxldjsn
22分钟前
3
0
Ubuntu16.04安装Qt5.12.2

Ubuntu16.04安装Qt5.12.2 第一步:下载文件 https://download.qt.io/official_releases/qt/5.12/5.12.2/ 第二步:安装依赖库 sudo apt-get install build-essential sudo apt-get install li......

shzwork
27分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部