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]。每一次查找与中间值比较,可以确定是否查找成功,不成功当前查找区间缩小一半。递归找,即可。

2.python代码:

复制代码 代码如下:

#!/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+Django搭建自己的blog网站

Python+Django搭建自己的blog网站

一、前言 1.1.环境 python版本:3.6 Django版本:1.11.6 1.2.预览效果 最终搭建的blog的样子,基本上满足需求了。框架搭好了,至于CSS,可以根据自己喜好随...

python SocketServer源码深入解读

python SocketServer源码深入解读

再看继承 真正的大餐来之前,还是来点儿开胃菜!回顾一下关于类的继承的知识: 我们先看上面的代码,这是一个简单的类继承,我们可以看到父类Base和子类Son,它们中各有一个Testf...

python实现二分查找算法

二分查找算法:简单的说,就是将一个数组先排序好,比如按照从小到大的顺序排列好,当给定一个数据,比如target,查找target在数组中的位置时,可以先找到数组中间的数array[mid...

MySQL最常见的操作语句小结

以下是我这几天一直在用的几个命令,先记下来,以后会整理一份mysql详细的使用文档 注:[]中代表名字,需要用库名或者表名替换 显示所有的库: show databases;...

Python实现以时间换空间的缓存替换算法

缓存是指可以进行高速数据交换的存储器,它先于内存与CPU交换数据,因此速度很快。缓存就是把一些数据暂时存放于某些地方,可能是内存,也有可能硬盘。 在使用Scrapy爬网站的时候,产生出来...