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

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

相关文章

解决Pytorch 加载训练好的模型 遇到的error问题

解决Pytorch 加载训练好的模型 遇到的error问题

这是一个非常愚蠢的错误 debug的时候要好好看error信息 提醒自己切记好好对待error!切记!切记! -----------------------分割线------------...

python Django里CSRF 对应策略详解

CSRF(Cross Site Request Forgery, 跨站域请求伪造)是一种网络的×××方式。 我的理解是,比如你访问过招商银行的网站并登陆之后,你的cookie信息暂时不会...

python简单实现获取当前时间

说起计算机中的时间,还有一些比较有意思的事,比如我们经常听到的Unix时间戳,UTC时间,格林威治时间等,从表示上来讲他们基本属于同一个东西,因为他们的时间表示都是从1970年.1月.1...

详解Python验证码识别

以前写过一个刷校内网的人气的工具,Java的(以后再也不行Java程序了),里面用到了验证码识别,那段代码不是我自己写的:-) 校内的验证是完全单色没有任何干挠的验证码,识别起来比较容易...

Python实现重建二叉树的三种方法详解

Python实现重建二叉树的三种方法详解

本文实例讲述了Python实现重建二叉树的三种方法。分享给大家供大家参考,具体如下: 学习算法中,探寻重建二叉树的方法: 用input 前序遍历顺序输入字符重建 前序遍历顺序字...