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三种遍历文件目录的方法实例代码

本文实例代码主要实现的是python遍历文件目录的操作,有三种方法,具体代码如下。 #coding:utf-8 # 方法1:递归遍历目录 import os def v...

python获得一个月有多少天的方法

本文实例讲述了python获得一个月有多少天的方法。分享给大家供大家参考。具体分析如下: 在python的datetime模块中没有一个月有多少天的方法,但是可以使用calendar模块...

Python循环结构的应用场景详解

前言 如果在程序中我们需要重复的执行某条或某些指令,例如用程序控制机器人踢足球,如果机器人持球而且还没有进入射门范围,那么我们就要一直发出让机器人向球门方向奔跑的指令。当然你可能已经注意...

Python如何使用Gitlab API实现批量的合并分支

这篇文章主要介绍了Python如何使用Gitlab API实现批量的合并分支,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 1.需求:...

kafka-python批量发送数据的实例

如下所示: from kafka import KafkaClient from kafka.producer import SimpleProducer def send_...