文档章节

人工智能你必须掌握的32个算法(一)二分搜索算法

木头释然
 木头释然
发布于 2018/07/16 08:38
字数 547
阅读 74
收藏 1

在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 从维基百科对于二分搜索的描述中可以发现: ①二分搜索的基础是必须是有序数组,并且是可比较的 ②假设数组为升序,选取中间元素与需要查找元素比较大小。如果当前元素与选取元素相等,则查找结束;如果当前元素比选取元素大,则选取当前元素的右侧元素,反之选取当前元素左侧元素。 ③重复步骤②直至查找指定元素或剩余元素数量为零 编程中我们需要注意两个问题: ①当数据数量为偶数时,如何选取中间值
②当有相同数据时如何处理 代码实现:

array = [1, 2, 3, 4, 5, 6, 7]
def binarySearch(array, value):
low = 0
high = len(array)-1
while low <= high:
    midd = (low+high)//2  # 取整 防止结果是小数
    if value == array[midd]:
        return array[midd]  # 选中结果  跳出循环
    elif value > array[midd]:
        low = midd+1 #大于当前值 选取右侧剩余数据
    else:
        high = midd-1 #小于当前值 选取左侧剩余数据
return None
print('result:' + str(binarySearch(array, 3)))

 

© 著作权归作者所有

木头释然
粉丝 18
博文 9
码字总数 5035
作品 0
西青
其他
私信 提问
【python】手把手带你掌握算法基础01_二分法和选择排序法的实现

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

徐胥
05/22
0
0
算法工程师成长计划

算法工程师成长计划 近年来,算法行业异常火爆,算法工程师年薪一般20万~100 万。越来越多的人学习算法,甚至很多非专业的人也参加培训或者自学,想转到算法行业。尽管如此,算法工程师仍然...

rainchxy
2017/10/23
0
0
送书 | 你一定能看懂的算法基础书(代码示例基于Python)

本文引自图灵教育《算法图解》 你一定能看懂的算法基础书;代码示例基于Python;400多个示意图,生动介绍算法执行过程;展示不同算法在性能方面的优缺点;教会你用常见算法解决每天面临的实际...

dqcfkyqdxym3f8rb0
2017/11/24
0
0
二分求幂算法:快速的求幂计算方式

二分求幂法是快速计算形如 (a^b) 的求幂运算的方法。朴素计算 (a^b) 的方式是将 (a) 连乘 (b) 次,代码如下: 参考资料: 王道论坛编组.王道论坛计算机考研机试指南[M]. :, 2013. 101-105....

faterazer
06/05
0
0
ACM进阶计划

ACM进阶计划 ACM队不是为了一场比赛而存在的,为的是队员的整体提高。 大学期间,ACM队队员必须要学好的课程有: l C/C++两种语言 l 高等数学 l 线性代数 l 数据结构 l 离散数学 l 数据库原理...

angel_kitty
2017/04/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

3_数组

3_数组

行者终成事
52分钟前
7
0
经典系统设计面试题解析:如何设计TinyURL(二)

原文链接:https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR 编者注:本文以一道经典的系统设计面试题:《如何设计TinyURL》的参考答案和解析为例,帮助...

APEMESH
今天
7
0
使用logstash同步MySQL数据到ES

概述   在生成业务常有将MySQL数据同步到ES的需求,如果需要很高的定制化,往往需要开发同步程序用于处理数据。但没有特殊业务需求,官方提供的logstash就很有优势了。   在使用logstas...

zxiaofan666
今天
10
0
X-MSG-IM-分布式信令跟踪能力

经过一周多的鏖战, X-MSG-IM的分布式信令跟踪能力已基本具备, 特点是: 实时. 只有要RX/TX就会实时产生信令跟踪事件, 先入kafka, 再入influxdb待查. 同时提供实时sub/pub接口. 完备. 可以完整...

dev5
今天
7
0
OpenJDK之CyclicBarrier

OpenJDK8,本人看的是openJDK。以前就看过,只是经常忘记,所以记录下 图1 CyclicBarrier是Doug Lea在JDK1.5中引入的,作用就不详细描述了,主要有如下俩个方法使用: await()方法,如果当前线...

克虏伯
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部