资讯专栏INFORMATION COLUMN

二分查找算法速记

chinafgj / 3103人阅读

摘要:二分查找英语,也称折半搜索英语对数搜索英语,是一种在有序数组中查找某一特定元素的搜索算法。这种搜索算法每一次比较都使搜索范围缩小一半。代码实现参考文章算法通关讲

二分查找(英语:binary search),也称折半搜索(英语:half-interval search)对数搜索(英语:logarithmic search,是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

适合的场景:

Sorted(单调递增或者递减)

Bounded (存在上下界,因为要一分为二的进行查找)

Accessible by index(能够通过索引访问)

时间复杂度:

O(logN)

空间复杂度:

O(N) 使用常数空间,无论任何大小的输入数据,算法使用的空间都是一样的

适用的数据结构:

数组,因为在内存中时连续的适合使用二分查找。但是链表不适合,因为链表坐标不是固定的,访问a[2]需要先从a[0]的后继节点找到a[1]再通过a[1]的后继节点才能访问到a[2]。

步骤:

初始状态left、right 分别指向数组的头和尾。

通过(left + right) /2 得到中间位置mid,访问数组中mid位置的元素。

判断其与查找目标的大小关系,相等则程序返回,

比目标小则挪动left指针到mid + 1;比目标大则挪动right指针到mid - 1

重复上面步骤2 ~ 3直到找到目标元素或者程序退出。

代码实现:


参考文章: 算法通关40讲

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/31333.html

相关文章

  • 数据结构与算法——二分查找

    摘要:所以,二分查找较适用于一次排序,多次查找的数据。面对大量的数据,二分查找方能体现其优势。 1. 二分查找的思想 二分查找是一种使用十分普遍的查找算法,其基本的思路也非常的简单,在一个有序的数据集合中,我们想要查找某个数据,直接取最中间的那个数据,将它和要找的数据进行比较,如果较大,则在更大的那个数值区间继续取中间值查找,反之亦然。 例如我们要在一个有序的集合里[1,3,5,6,7,8,...

    boredream 评论0 收藏0
  • PHP算法二分查找

    摘要:二分查找的定义二分查找也称折半查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。算法的要求从上面的定义我们可以知道,满足该算法的要求必须如下两点必须采用顺序存储结构。 showImg(https://segmentfault.com/img/remote/1460000016466416?w=800&h=191); 二分查找的...

    Soarkey 评论0 收藏0
  • 数据结构与算法二分查找

    摘要:为检查长度为的列表,二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树,戳这里数据结构与算法二叉树算法常见练习在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构(必须理解和掌握) 有序数据结构:栈、队列、链表。有序数据结构省空间(储存空间小) 无序数据结构:集合、字典、散列表,无序...

    zsirfs 评论0 收藏0
  • 数据结构与算法二分查找

    摘要:为检查长度为的列表,二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树,戳这里数据结构与算法二叉树算法常见练习在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构(必须理解和掌握) 有序数据结构:栈、队列、链表。有序数据结构省空间(储存空间小) 无序数据结构:集合、字典、散列表,无序...

    you_De 评论0 收藏0
  • 数据结构与算法二分查找

    摘要:为检查长度为的列表,二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树,戳这里数据结构与算法二叉树算法常见练习在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 常见数据结构 简单数据结构(必须理解和掌握) 有序数据结构:栈、队列、链表。有序数据结构省空间(储存空间小) 无序数据结构:集合、字典、散列表,无序...

    gotham 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<