文档章节

python二分法实例代码

mysoftsky
 mysoftsky
发布于 2014/04/08 12:56
字数 291
阅读 43
收藏 0

分享一个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 -*-
#www.jbxue.com
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);

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

本文转载自:

mysoftsky
粉丝 7
博文 176
码字总数 4429
作品 0
廊坊
私信 提问
python实现lower_bound和upper_bound

由于对于二分法一直都不是很熟悉,这里就用C++中的lowerbound和upperbound练练手。这里用python实现 lowerbound和upperbound本质上用的就是二分法,lowerbound查找有序数组的第一个小于等于目...

mambakb
2018/11/29
0
0
【python】手把手带你掌握算法基础01_二分法和选择排序法的实现

一、大O表示法 学算法就绕不开大O表示法,大O法可以告诉我们算法的时间和空间复杂度。 我们先聊点简单的,请你从1数到10,这里的复杂度是多少呢?O(10)。那么从1数到n,归纳法告诉我们,复...

徐胥
05/22
0
0
python 二分插入、遍历目录

这两道题是之前面试测试开发遇到的,今天分享给大家。 遍历文件 python 遍历文件夹下所有文件,并打印出所有文件名 二分法 python 在顺序列表中,二分法查找且插入一个数

lvyz0207
2018/05/24
0
0
《算法图解》笔记(1) 二分查找

二分查找 二分查找是一种算法,其输入是一个有序的元素列表。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回 null 。 一般而言,对于包含n个元素的列表,用二分查找最多需要l...

WMXNLFD
03/05
0
0
python模块介绍- bisect-有序列表

python模块介绍- bisect 2013-03-21 磁针石 #承接软件自动化实施与培训等gtalk:ouyangchongwu#gmail.com qq 37391319 博客:http://blog.csdn.net/oychw #版权所有,转载刊登请来函联系 # 深...

长平狐
2013/12/25
139
0

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
5
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
昨天
6
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
7
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部