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实现制度转换(货币,温度,长度)

人民币和美元是世界上通用的两种货币之一,写一个程序进行货币间币值转换,其中: 人民币和美元间汇率固定为:1美元 = 6.78人民币。 程序可以接受人民币或美元输入,转换为美元或人民币输出...

pandas按行按列遍历Dataframe的几种方式

pandas按行按列遍历Dataframe的几种方式

遍历数据有以下三种方法: 简单对上面三种方法进行说明: iterrows(): 按行遍历,将DataFrame的每一行迭代为(index, Series)对,可以通过row[n...

Python爬豆瓣电影实例

Python爬豆瓣电影实例

文件结构 html_downloader.py - 下载网页html内容 #!/usr/bin/python # -*- coding: UTF-8 -*- import urll...

python实现拓扑排序的基本教程

python实现拓扑排序的基本教程

拓扑排序 几乎在所有的项目,甚至日常生活,待完成的不同任务之间通常都会存在着某些依赖关系,这些依赖关系会为它们的执行顺序行程表部分约束。对于这种依赖关系,很容易将其表示成一个有向无环图(...

使用python绘制二元函数图像的实例

废话少说,直接上代码: #coding:utf-8 import numpy as np import matplotlib.pyplot as plt from mpl_toolk...