Python实现二分法算法实例
作者:junjie 发布时间:2021-06-23 19:31:12
标签: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);
注意:二分查找的前提必须待查找的序列有序。
0
投稿
猜你喜欢
- 前言在浏览博客时,偶然看到了用python将汉字转为拼音的第三方包,但是在实现的过程中发现一些参数已经更新,现在将两种方法记录一下。xpin
- HTML5 越来越引起人们的关注,苹果甚至将 HTML5 视为 Flash 的掘墓人 。然而,作为一种尚未成型的技术,HTML5 对很多人来
- 这篇文章主要介绍了基于Python获取城市近7天天气预报,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的
- 经常由于各种压缩格式的不一样用到文件的解压缩时就需要下载不同的解压缩工具去处理不同的文件,以至于桌面上的压缩工具就有三四种,于是使用pyth
- 开始之前当然要导入模块啦:>>> import pymongo下一步,必须本地mongodb服务器的安装和启动已经完成,才
- 装饰器总结什么是装饰器?处理函数的函数,加一个功能,但是不影响原来函数的内部结构生活中的例子:给手机加一个外壳,外壳保护了手机装饰器有什么用
- 本文详细讲述了DRF认证组件的原理以及用法.源码剖析讲解DRF版本的时候我们都知道了,在dispatch方法里执行了initial方法来初始
- 1. 函数式编程概述1.1. 什么是函数式编程?函数式编程使用一系列的函数解决问题。函数仅接受输入并产生输出,不包含任何能影响产生输出的内部
- 1.安装pyqt51.打开anaconda prompt命令窗口,激活虚拟环境:activate tensorflow2.安装PyQt5pi
- 本文实例讲述了Python日志logging模块功能与用法。分享给大家供大家参考,具体如下:本文内容:logging模块的介绍logging
- 首先导入包含apriori算法的mlxtend库,pip install mlxtend调用apriori进行关联规则分析,具体代码如下,其
- json_encode()如何转化一个对象? 使用 json_encode() 将数组 array
- 神经网络玩得越久就越会尝试一些网络结构上的大改动。先说意图有两个模型:模型A和模型B。模型A的输出可以连接B的输入。将两个小模型连接成一个大
- 如何利用pandas读取csv数据并绘图导包,常用的numpy和pandas,绘图模块matplotlib,import matplotli
- 本文实例讲述了Python编程之多态用法。分享给大家供大家参考。具体分析如下:什么是多态?顾名思义,多态就是多种表现形态的意思。它是一种机制
- 一、json_encode()该函数主要用来将数组和对象,转换为json格式。先看一个数组转换的例子:$arr = array ('
- 一、 官网下载安装包: 官网网址:https://www.python.org/ 我下载的是3.6.3版本,如下图:&n
- HTTP、HTTPS协议下session共享解决cookie失效 的办法:(也许不是最好的,但是实用)原理就是把session id设置到本
- 1.样式的重用性CSS布局的网页最大的特点就是样式的可重用性,利用class选择符重复将某个样式属性多次在网页中使用,以减少不断定义样式属性
- 序列化(Serialization)与反序列化(Deserialization)是RESTful API 开发中绕不开的一环,开发时,序列化