Python实现二分法算法实例

yipeiwu_com6年前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定时检测无响应进程并重启的实例代码

总有一些程序在windows平台表现不稳定,动不动一段时间就无响应,但又不得不用,每次都是发现问题了手动重启,现在写个脚本定时检测进程是否正常,自动重启。 涉及知识点 schedu...

pow在python中的含义及用法

pow()方法返回xy(x的y次方) 的值 语法 以下是math模块pow()方法的语法: import math math.pow( x, y ) 内置的pow()方法 p...

Python+Pika+RabbitMQ环境部署及实现工作队列的实例教程

Python+Pika+RabbitMQ环境部署及实现工作队列的实例教程

rabbitmq中文翻译的话,主要还是mq字母上:Message Queue,即消息队列的意思。前面还有个rabbit单词,就是兔子的意思,和python语言叫python一样,老外还是...

Python机器学习算法之k均值聚类(k-means)

Python机器学习算法之k均值聚类(k-means)

一开始的目的是学习十大挖掘算法(机器学习算法),并用编码实现一遍,但越往后学习,越往后实现编码,越发现自己的编码水平低下,学习能力低。这一个k-means算法用Python实现竟用了三天...

python opencv实现运动检测

本文实例为大家分享了python opencv运动检测的具体代码,供大家参考,具体内容如下 # -*- coding:utf-8 -*- __author__ = 'kingking...