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 列表推导式使用详解

所谓的列表推导式,就是指的轻量级循环创建列表。 基本使用方式 # 创建一个0-10的列表 a = [x for x in range(11)] print(a) """ 输出结果:...

python连接、操作mongodb数据库的方法实例详解

本文实例讲述了python连接、操作mongodb数据库的方法。分享给大家供大家参考,具体如下: 数据库连接 from pymongo import MongoClient imp...

Django + Uwsgi + Nginx 实现生产环境部署的方法

Django + Uwsgi + Nginx 实现生产环境部署的方法

如何在生产上部署Django? Django的部署可以有很多方式,采用nginx+uwsgi的方式是其中比较常见的一种方式。 uwsgi介绍 uWSGI是一个Web服务器,它实现...

python3 字符串/列表/元组(str/list/tuple)相互转换方法及join()函数的使用

在抓取网络数据的时候,有时会用正则对结构化的数据进行提取,比如 href="https://www.1234.com"等。python的re模块的findall()函数会返回一个所有匹配...

Python单元测试框架unittest使用方法讲解

概述 1.测试脚手架(test fixture) 测试准备前要做的工作和测试执行完后要做的工作.包括setUp()和tearDown(). 2.测试案例(test case) 最小的测试...