Python实现二分法算法实例

yipeiwu_com5年前Python基础

1.算法:(设查找的数组期间为array[low, high])

(1)确定该期间的中间位置K
(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。区域确定如下:

a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……,K-1]
b.array[k]<T 类似上面查找区间为array[k+1,……,high]。每一次查找与中间值比较,可以确定是否查找成功,不成功当前查找区间缩小一半。递归找,即可。

复制代码 代码如下:

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

def BinarySearch(array,t):
low = 0
height = len(array)-1
while low <= height:
mid = (low+height)/2
if array[mid] < t:
low = mid + 1

elif array[mid] > t:
height = mid - 1

else:
return array[mid]

return -1

if __name__ == "__main__":
print BinarySearch([1,2,3,34,56,57,78,87],57)

结果:57

3.时间复杂度:O(log2n);

注意:二分查找的前提必须待查找的序列有序。

相关文章

浅析Python中signal包的使用

在liunx系统中要想每隔一分钟执行一个命令,最普遍的方法就是crontab了,如果不想使用crontab,经同事指点在程序中可以用定时器实现这种功能,于是就开始摸索了,发现需要一些信号...

python3解析库BeautifulSoup4的安装配置与基本用法

前言 Beautiful Soup是python的一个HTML或XML的解析库,我们可以用它来方便的从网页中提取数据,它拥有强大的API和多样的解析方式。 Beautiful Soup的...

在Mac OS上搭建Python的开发环境

一. 安装python mac系统其实自带了一个python的执行执行环境,用来运行python还行,但是开发可能就不够了,因此我们需要重新安装python。这里有两种方案安装: 1.h...

Python 使用 PyMysql、DBUtils 创建连接池提升性能

Python 使用 PyMysql、DBUtils 创建连接池提升性能

Python 编程中可以使用 PyMysql 进行数据库的连接及诸如查询/插入/更新等操作,但是每次连接 MySQL 数据库请求时,都是独立的去请求访问,相当浪费资源,而且访问数量达到一...

Python使用QQ邮箱发送Email的方法实例

Python使用QQ邮箱发送Email的方法实例

前言 其实Python使用QQ邮箱发送Email代码很简单,短短几行代码就可以实现这个功能。 使用到的模块有smtplib和email这个两个模块,关于这两个模块的方法就不多说了。不了...