python二分法实现实例_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);

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

时间: 2024-11-20 14:39:08

python二分法实现实例_python的相关文章

Python二分法搜索算法实例分析

  这篇文章主要介绍了Python二分法搜索算法,实例分析了Python实现二分法的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下 今天看书时,书上提到二分法虽然道理简单,大家一听就明白但是真正能一次性写出别出错的实现还是比较难的,即使给了你充足的时间,比如1小时.如果你不是特别认真的话,可能还是会出一些这样那样的错误,所以就尝试了自己去实现一下,看能否一次通过,结果自然不言而喻,虽然用的时间不长,但是我失败了,呵呵. 个人觉得失败的最主要原因是自己没有认真的先想好这个思路和可能出现的分支

gearman的安装启动及python API使用实例_python

本文讲述了gearman的安装启动及python API使用实例,对于网站建设及服务器维护来说非常有用! 一.概述: Gearman是一款非常优秀的任务分发框架,可以用于分布式计算.具体的gearmand服务的安装启动及gearman的python 模块的安装以及简单示例如下:   操作系统:rnel 5.7 1. 首先,我们需要安装gearmand,在centos和rhel环境下,我们只需运行以下命令: yum install gearmand -y   注意:如果不希望通过yum的方式来安装

Python创建日历实例_python

本文讲述了Python创建日历的方法,与以往不同的是,本文实例不使用Python提供的calendar实现,相信对大家的Python程序设计有一定的借鉴价值. 此程序在windows下测试通过,由于python字符编码直接输出给操作系统,so win下以gbk ansi为准,linux下大概以utf-8为准(未测试) #coding=gbk # -*- coding: cp936 -*- # 制作一个日历(只显示阳历日期) '''实现方法:不使用python提供的calendar,根据给出的日期

python列表操作实例_python

本文实例讲述了python列表操作的方法.分享给大家供大家参考. 具体实现方法如下: 复制代码 代码如下: class Node:    """Single node in a data structure"""      def __init__(self, data):       """Node constructor"""              self._data = da

python操作gmail实例_python

本文实例讲述了python操作gmail的方法.分享给大家供大家参考. 具体实现方法如下: 复制代码 代码如下: import imaplib, re   class pygmail(object):     def __init__(self):         self.IMAP_SERVER='imap.gmail.com'         self.IMAP_PORT=993         self.M = None         self.response = None      

python多进程操作实例_python

由于CPython实现中的GIL的限制,python中的多线程其实并不是真正的多线程,如果想要充分地使用多核CPU的资源,在python中大部分情况我们需要使用多进程. 这也许就是python中多进程类库如此简洁好用的原因所在.在python中可以向多线程一样简单地使用多进程. 一.多进程 process的成员变量和方法: >>class multiprocessing.Process([group[, target[, name[, args[, kwargs]]]]]) 来的定义类似于th

python字典序问题实例_python

本文实例讲述了python字典序问题,分享给大家供大家参考.具体如下: 问题描述: 将字母从左向右的次序与字母表中的次序相同,且每个字符最大出现一次..例如:a,b,ab,bc,xyz等都是升序的字符串.现对字母表A产生的所有长度不超过6的升序字符串按照字典充排列并编码如下: 1 2 .. 26 27 28 ... a b .. z ab ac .. 对一个升序字符串,迅速计算出它在上述字典中的编码. 实现代码如下: import string all_letter = string.ascii

python测试驱动开发实例_python

本文实例讲述了python测试驱动开发的方法,分享给大家供大家参考.具体方法如下: import unittest from main import Sample class SampleTest(unittest.TestCase): def setUp(self): print "create a new Sample" self._sample = Sample("b64e5843ca7db8199c405be565fa7f57") def tearDown(

python多线程操作实例_python

一.python多线程 因为CPython的实现使用了Global Interpereter Lock(GIL),使得python中同一时刻只有一个线程在执行,从而简化了python解释器的实现,且python对象模型天然地线程安全.如果你想你的应用程序在多核的机器上使用更好的资源,建议使用multiprocessing或concurrent.futures.processpoolexecutor.但是如果你的程序是IO密集型,则使用线程仍然是很好的选择. 二.python多线程使用的两种方法