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);

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

相关文章

unittest+coverage单元测试代码覆盖操作实例详解

unittest+coverage单元测试代码覆盖操作实例详解

基于上一篇文章,这篇文章是关于使用coverage来实现代码覆盖的操作实例,源代码在上一篇已经给出相应链接。 本篇文章字用来实现代码覆盖的源代码,整个项目的测试框架如下: 就是在源代码...

python实现决策树

本文实例为大家分享了python实现决策树的具体代码,供大家参考,具体内容如下 算法优缺点: 优点:计算复杂度不高,输出结果易于理解,对中间值缺失不敏感,可以处理不相关的特征数据 缺...

python 使用re.search()筛选后 选取部分结果的方法

python 使用re.search()筛选后 选取部分结果的方法

使用group()方法 b = 'hello good fine' re.search(r'^hello\s(.*)\sfine',b).group() group() 会...

python中的常量和变量代码详解

局部和全局变量: # name='lhf' # def change_name(): # # global name # name='帅了一比' # print('cha...

python中scikit-learn机器代码实例

我们给大家带来了关于学习python中scikit-learn机器代码的相关具体实例,以下就是全部代码内容: # -*- coding: utf-8 -*- import num...