文档章节

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

黄哥Python培训
 黄哥Python培训
发布于 2016/04/05 06:31
字数 869
阅读 354
收藏 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
626
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

没有更多内容

加载失败,请刷新页面

加载更多

代理模式之JDK动态代理 — “JDK Dynamic Proxy“

动态代理的原理是什么? 所谓的动态代理,他是一个代理机制,代理机制可以看作是对调用目标的一个包装,这样我们对目标代码的调用不是直接发生的,而是通过代理完成,通过代理可以有效的让调...

code-ortaerc
今天
4
0
学习记录(day05-标签操作、属性绑定、语句控制、数据绑定、事件绑定、案例用户登录)

[TOC] 1.1.1标签操作v-text&v-html v-text:会把data中绑定的数据值原样输出。 v-html:会把data中值输出,且会自动解析html代码 <!--可以将指定的内容显示到标签体中--><标签 v-text=""></......

庭前云落
今天
7
0
VMware vSphere的两种RDM磁盘

在VMware vSphere vCenter中创建虚拟机时,可以添加一种叫RDM的磁盘。 RDM - Raw Device Mapping,原始设备映射,那么,RDM磁盘是不是就可以称作为“原始设备映射磁盘”呢?这也是一种可以热...

大别阿郎
今天
10
0
【AngularJS学习笔记】02 小杂烩及学习总结

本文转载于:专业的前端网站☞【AngularJS学习笔记】02 小杂烩及学习总结 表格示例 <div ng-app="myApp" ng-controller="customersCtrl"> <table> <tr ng-repeat="x in names | orderBy ......

前端老手
昨天
14
0
Linux 内核的五大创新

在科技行业,创新这个词几乎和革命一样到处泛滥,所以很难将那些夸张的东西与真正令人振奋的东西区分开来。Linux内核被称为创新,但它又被称为现代计算中最大的奇迹,一个微观世界中的庞然大...

阮鹏
昨天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部