python实现二分查找算法_python实现二分查找算法

二分查找算法也成为折半算法，对数搜索算法，一会中在有序数组中查找特定一个元素的搜索算法。搜索过程是从数组中间元素开始的

如果中间元素正好是要查找的元素，则搜索过程结束；如果查找的数大于中间数，则在数组的前一半查找，否则，在后一半查找。直到找到相应

数据止。

该算法的的复杂度为 O(log n)，相比其他算法优势还是比较明显的。

二分查找法的O(log n)让它成为十分高效的算法。不过它的缺陷却也是那么明显的。就在它的限定之上：

必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。

数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组变成低效的事情。

python的代码实现和测试：

def binary_search(a_list,item):

first = 0

last = len(a_list) - 1

found = False

while first <= last and not found:

midpoint = (first + last) // 2

if a_list[midpoint] == item:

found = True

else:

if item < a_list[midpoint]:

last = midpoint - 1

else:

first = midpoint + 1

return found

test_list = [0,1,2,8,13,17,19,32,42,]

print(binary_search(test_list,3))

print(binary_search(test_list,13))

def dbinary_search(a_list, item):

if len(a_list) == 0:

return False

else:

midpoint = len(a_list) // 2

if a_list[midpoint] == item:

return True

else:

if item < a_list[midpoint]:

return binary_search(a_list[:midpoint], item)

else:

binary_search(a_list[midpoint + 1:], item)

print(dbinary_search(test_list,3))

print(dbinary_search(test_list,13))

Python递归函数,二分查找算法

目录 一.初始递归 二.递归示例讲解 二分查找算法 一.初始递归 递归函数:在一个函数里在调用这个函数本身. 递归的最大深度:998 正如你们刚刚看到的,递归函数如果不受到外力的阻止会一直执行下去.但 ...

【Python】二分查找算法

二分查找:在一段数字内,找到中间值,判断要找的值和中间值大小的比较.如果中间值大一些,则在中间值的左侧区域继续按照上述方式查找.如果中间值小一些,则在中间值的右侧区域继续按照上述方式查找.直到找到我们 ...

python函数(4)：递归函数及二分查找算法

人理解循环,神理解递归!  一.递归的定义 def story(): s = \"\"\" 从前有个山,山里有座庙,庙里老和尚讲故事, 讲的什么呢? \"\"& ...

二分查找算法(Python版)

[本文出自天外归云的博客园] 记性不好(@.@),所以平时根本用不到的东西就算学过如果让我去想也会需要很多时间(*.*)! 二分查找算法 在一个有序数组中查找元素最快的算法,也就是折半查找法,先找一个 ...

Python——递归、二分查找算法

递归函数 1. 递归 (1)什么是递归:在函数中调用自身函数(2)最大递归深度:默认997/998——是Python从内存角度出发做的限制 n = 0 def story(): global n n+ ...

两种方法实现Python二分查找算法

两种方法实现Python二分查找算法   一. ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 arr=[1,3,6,9,10,20,30] def findnumber( ...

Python递归函数和二分查找算法

递归函数:在一个函数里在调用这个函数本身. 递归的最大深度:998 正如你们刚刚看到的,递归函数如果不受到外力的阻止会一直执行下去.但是我们之前已经说过关于函数调用的问题,每一次函数调用都会产生一个属 ...

python之路——二分查找算法

楔子 如果有这样一个列表,让你从这个列表中找到66的位置,你要怎么做? l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72 ...

Python学习日记(十三) 递归函数和二分查找算法

什么是递归函数? 简单来说就是在一个函数中重复的调用自己本身的函数 递归函数在调用的时候会不断的开内存的空间直到程序结束或递归到一个次数时会报错 计算可递归次数: i = 0 def func(): ...

随机推荐

BPM配置故事之案例9-根据表单数据调整审批线路2

老李:好久不见啊,小明. 小明:-- 老李:不少部门有物资着急使用,现在的审批流程太慢了,申请时增加一个是否加急的选项吧.如果选加急,金额1000以下的直接到我这里,我审批完就通过,超过1000的直接 ...

[Asp.net 5] Logging-其他日志系统的实现

Microsoft.Framework.Logging.NLog 使用Nlog扩展日志系统:按照我们上节说的,对于扩展的日志系统都要实现俩个接口ILogger.ILoggerProvider.所以在当 ...

C# 我是个传奇的 using

呵呵呵: ----------------------------------------------------------------------------------------------- ...

Linux五种IO模型性能分析

1. 概念理解 在进行网络编程时,我们常常见到同步(Sync)/异步(Async),阻塞(Block)/非阻塞(Unblock)四种调用方式: 同步:       所谓同步,就是在发出一个功能调用时, ...

Android Studio | 详细安装教程

Windows和Mac系统下的安装教程差不多,需要注意的是确保系统中已经安装了JDK,并且JDK版本为1.7或1.7以上版本,如果没有,请自行更新下载安装,地址如下: Java SE Develop ...

plsql developer无法识别32位oracle问题如何解决？

1.登录PL/SQL Developer这里省略Oracle数据库和PL/SQL Developer的安装步骤,注意在安装PL/SQL Developer软件时,不要安装在Program Files ...

Linux常用命令4(grep、df、du、awk、su、ll)

[grep命令] grep常用用法 [root@www ~]# grep [-acinv] [--color=auto] \'搜寻字符串\' filename选项与参数:-a :将 binary 文件以 ...

ASP.NET Web Pages 的冲突版本问题

随着VS版本和.NET MVC版本.EF的版本的不断更新,虽然很多功能随着版本的提升而更完善,但对于旧版本开发的软件就有点悲催了,或许很多开发者都遇到类似的问题! 最近有一个项目是用.NET MVC3 ...

nginx支持pathinfo的方法，亲测有效的

修改配置文件,修改特点域名的配置文件 location ~ \\.php { #去掉$ root H:/PHPServer/WWW; fastcgi_pass ; fastcgi_index index ...

css中可以继承的属性

声明 : 本文源于https://www.cnblogs.com/thislbq/p/5882105.html CSS中可以和不可以继承的属性   一.无继承性的属性 1.display:规定元素应该 ...