python二分法实现实例
发布时间：2023-02-16 05:09:46
标签：二分法
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);
注意：二分查找的前提必须待查找的序列有序。
0
投稿猜你喜欢
- 批量更新mysql更新语句很简单，更新一条数据的某个字段，一般这样写：UPDATE mytable SET myfield = 'v
Python中的type()函数和isinstance()函数是两个常用的类型判断函数，它们可以用来判断变量的类型，接下来让我们一起来看一下- 1、官网说法在下次 DOM 更新循环结束之后执行延迟回调。在修改数据之后立即使用这个方法，获取更新后的 DOM。核心点有2个：DOM 更新和
- 本文实例为大家分享了three.js 全景重力感应的具体代码，供大家参考，具体内容如下实现three.js 全景图 demo使用three.
- 本文实例为大家分享了微信小程序实现扫雷游戏的具体代码，供大家参考，具体内容如下实验小提醒，打开微信小程序模板时，一定要看清楚，要选js模板，
- 描述log10() 方法返回以10为基数的x对数，x>0。语法以下是 log10() 方法的语法:import mathmath.lo
- 一、需求来源：如果用户在文本框中填了一段<script>alert(xxx);</script>代码，然后我们还保存
- 前言虚拟环境是程序执行时的独立执行环境，在同一台服务器中可以创建不同的虚拟环境供不同的系统使用，项目之间的运行环境保持独立性而相互不受影响。
- 前言Hello！大家好，有好几天没有跟大家见面咯~不知道大家是否在等待《小玩意儿》专栏的更新呢上一篇的文章【老师见打系列】：我只是写了一个自
- Mac键盘符号和修饰键说明⌘ Command⇧ Shift⌥ Option⌃ Control↩︎ Return/Enter⌫ Delete⌦
- 下面记录一下在本地 Windwos 环境用 vagrant 搭建的虚拟机（Homestaead）和生产环境阿里云 CentOS 系统安装 N
- 初学python,小缘缘出了几道题： 有一 list a = [1, 2, 3, 4, 5, 6] 请将 a 依 0, 1 1, 2 2,
- python脚本实现xlsx文件解析，供大家参考，具体内容如下环境配置：1.系统环境：Windows 7 64bit 2.编译环境：Pyth
- Keras的底层库使用Theano或TensorFlow，这两个库也称为Keras的后端。无论是Theano还是TensorFlow，都需要
- 在开发过程中，收到这样一个问题反馈，在网站上传 100 MB 以上的文件经常失败，重试也要等老半天，这就难为需要上传大规格文件的用户了。那么
- 本文实例讲述了golang实现unicode转换为字符串string的方法。分享给大家供大家参考，具体如下：package mainimpo
- 众所周知windows平台漏洞百出，补丁一个接一个，但总是补也补不净。我把我所知道的看asp源码的方法总结了一下，并且用c#写了个应用程序来
- 本文实例讲述了python 实现的发送邮件模板。分享给大家供大家参考，具体如下：##发送普通txt文件（与发送html邮件不同的是邮件内容设
- 代码如下:DECLARE @T varchar(255), @C varchar(255) DECLARE Table_Cursor CUR
- 算法是计算机科学中一个重要的研究方向，是解决复杂问题的关键。在计算机世界中，算法无处不在。数据库是存储数据和执行大批量计算的场所，在数据库中
