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
投稿
猜你喜欢
- 我就废话不多说了,大家还是直接看代码吧!import kerasimport numpy as npfrom keras.applicati
- 本文实例讲述了php绘制圆形的方法。分享给大家供大家参考。具体实现方法如下:php绘图的基本步骤,有四步(php.ini里的 extensi
- 1.python中列表list的拷贝,会有什么需要注意的呢? python变量名相当于标签名。list2=list1 ,直接赋值,实质上指向
- 在Python中将字符串转换为集合使用 set() 类将字符串转换为集合,例如 my_set = set(my_str)。 set() 类将
- 当我们使用访问一个没有声明的变量时,JS会报错;而当我们给一个没有声明的变量赋值时,JS不会报错,相反它会认为我们是要隐式申明一个全局变量。
- 本文实例讲述了Python注释、分支结构、循环结构、伪“选择结构”用法。分享给大家供大家参考,具体如下:注释:python使用#作为行注释符
- 本文实例讲述了Python基于回溯法子集树模板解决野人与传教士问题。分享给大家供大家参考,具体如下:问题在河的左岸有N个传教士、N个野人和一
- 写入文件使用open()函数和write()函数但是有两种写法,分别是'a'和'w'。'a'
- 代码如下#!/bin/python#coding=utf-8#python-version=2.75  
- 从而达到方便快捷的目的,但是它在存储信息的时候往往会有一些敏感的东西,这些东西可能成为被攻击的目标,如银行的账号、信用卡事务或档案记录等。这
- 熟悉js的朋友很多都遇到过js的数组与字符串相互转换的情况,本文就此作一简单介绍,示例如下:一、数组转字符串需要将数组元素用某个字符连接成字
- Request.Cookies.Clear()这个方法并不是删除Cookie 删除 Cookie(即从用户的硬盘中物理移除 Cookie)是
- 从codered到nimda等,一大堆蠕虫把原来需要人工利用的漏洞都变成了程序自动利用了,大家还想去手工操作这些IIS漏洞么?让我们调整重心
- 小毅的blog:http://andymao.com/前天网上有个朋友发给我一个页面让我帮她看一下为什么鼠标翻转实现不了。我打开源文件看了一
- 大名鼎鼎的FCKeditor终于在最近发布新版本了,与增加版本号不同,这次完全把它改名了,更名为CKeditor。这应该是和它的开发公司CK
- cache 是一个带索引带超时的缓存库目的在于优化代码结构,提供了若干实践。 https://github.com/weapons
- <?php interface js{ function ys($a,$b); } class Af implements js{ f
- Abs (数值)绝对值。一个数字的绝对值是它的正值。空字符串 (null) 的绝对值,也是空字符串。未初始化的变数,其绝对为 0例子:ABS
- 这回我们看看如何实现判断两个对像的内容是否相等。这里有一个克隆结果原则是针对Java语言的,当然JavaScript也可以胜任。克隆满足的条
- 如何在约定时间显示特定的提示信息?<%Function Greeting()