首页 / 办公指南 / 什么是二分查找算法,二分查找算法的原理
什么是二分查找算法,二分查找算法的原理
如果各位朋友们也在进行数据结构与算法的相关学习的话,那么,大家自然就知道在 java 中也许多非常常用的查找方法,其中,二分查找算法就是最广为人知的一种方法,不知道大家自己有没有研究过二分查找算法呢?为了照顾到有一些朋友们并不是很了解二分查找算法,下面福昕知翼的小编还是会从什么是二分查找算法､二分查找算法的原理两个问题入手,为大家介绍二分查找算法｡
什么是二分查找算法
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法｡但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列｡
二分查找算法的原理
1. 如果待查序列为空,那么就返回-1.并退出算法;这表示查找不到目标元素｡
2. 如果待查序列不为空,则将它的中间元素与要查找的目标元素进行匹配,看它们是否相等｡
3. 如果相等,则返回该中间元素的索引,并退出算法;此时就查找成功了｡
4. 如果不相等,就再比较这两个元素的大小｡
5. 如果该中间元素大于目标元素,那么就将当前序列的前半部分作为新的待查序列;这是因为后半部分的所有元素都大于目标元素,它们全都被排除了｡
6. 如果该中间元素小于目标元素,那么就将当前序列的后半部分作为新的待查序列;这是因为前半部分的所有元素都小于目标元素,它们全都被排除了｡
7. 在新的待查序列上重新开始第1步的工作｡
二分查找之所以快速,是因为它在匹配不成功的时候,每次都能排除剩余元素中一半的元素｡因此可能包含目标元素的有效范围就收缩得很快,而不像顺序查找那样,每次仅能排除一个元素｡
本文就来探究几个最常用的二分查找场景:寻找一个数､寻找左侧边界､寻找右侧边界｡
而且,我们就是要深入细节,比如while循环中的不等号是否应该带等号,mid 是否应该加一等等｡分析这些细节的差异以及出现这些差异的原因,保证你能灵活准确地写出正确的二分查找算法｡
什么是二分查找算法?二分查找算法的原理是什么?相关的内容已经由福昕知翼的小编在上文为各位朋友们介绍完毕了,大家现在已经知道什么是二分查找算法,如果大家想要学好java的话,自然是需要掌握好二分查找算法了,在了解了二分查找算法的基本原理之后,大家可以更加轻松的掌握住它｡
本文地址: https://www.docer365.com/zn-1620.html
版权声明:除非特别标注,否则均为本站原创文章,转载时请以链接形式注明文章出处.
