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中处理字符串之isalpha()方法的使用

 isalpha()方法检查字符串是否仅由字母组成。 语法 以下是islpha()方法的语法: str.isalpha() 参数   &nb...

Python 解码Base64 得到码流格式文本实例

我就废话不多说了,直接上代码吧! # coding:utf8 import base64 def BaseToFlow(): while True: str =...

在Python的Django框架中实现Hacker News的一些功能

逐步指示 这是提供给更喜欢阅读的人的视频文本版本。我们将创建一个类似黑客新闻 或Reddit的社交新闻网站。它将被称为“钢铁传闻”,作为一个分享关于“钢铁侠”的有趣传闻和对其进行投票的地...

Python语言进阶知识点总结

Python语言进阶知识点总结

数据结构和算法 算法:解决问题的方法和步骤 评价算法的好坏:渐近时间复杂度和渐近空间复杂度。 渐近时间复杂度的大O标记: - 常量时间复杂度 - 布隆过滤器 / 哈希存储 - 对数时间复...

Python实现二叉树结构与进行二叉树遍历的方法详解

Python实现二叉树结构与进行二叉树遍历的方法详解

二叉树的建立 使用类的形式定义二叉树,可读性更好 class BinaryTree: def __init__(self, root): self.key = ro...