二分查找
二分查找是一种高效算法,它在排序列表中搜索所需的或目标元素。例如,给定一个测试分数的排序列表,如果老师想确定班上是否有人得分
二进位搜索的工作原理是将目标值与数组中间的元素进行比较。如果目标值大于中间元素,则从搜索空间中删除列表的左半部分,并在右半部分继续搜索。如果目标值小于中间值,则从搜索空间中删除右半部分,并在左半部分继续搜索。重复这个过程,直到中间的元素等于目标值,或者如果算法返回该元素根本不在列表中。
二分查找
二进位搜索检查已排序的列表,看所需的元素是否在列表中。它通过在程序的每次迭代期间将搜索空间减半来有效地做到这一点。基本上,二元搜索找到列表的中间,问"我要找的元素是比这个大还是小? "然后,它将列表中的搜索空间减半,如果元素较小,则只在左侧列表中搜索,如果元素较大,则只在右侧列表中搜索。它重复这个过程,直到找到要查找的元素(或者报告该元素根本不在列表中)。该算法使用了
简单来说,该算法的工作原理如下:
下面假设索引为零,这意味着列表最左边的元素是
th元素。
的层的值来确定排序列表的中间元素
低+高,其中low为列表的最低索引,high为列表的最高索引。在列表中 1,2,3.,4], (因为2出现在索引1)将是中间。在列表中 1,2,3.,4,5], (因为3出现在索引2处)是中间的。 将中间元素的值与目标值进行比较。
如果目标值等于中间的元素,则返回该元素在列表中为真(如果元素在列表中的位置是需要的,则还返回索引)。
如果目标值小于中间元素,则从搜索中消除中间元素(并包括)右侧的所有元素,并使用这个较小的搜索空间返回到第一步。
如果目标值大于中间元素,则从搜索中消除中间元素(并包括)左侧的所有元素,并使用这个较小的搜索空间返回到第一步。
二分搜索的一个限制是它只能在预先排序的列表中搜索。如果列表没有预先排序,二分搜索将不起作用。
显示二分搜索将执行的步骤来确定
4在以下列表中: =[0,2,5,5,9,10,11,12,14,15].在确定中间元素时向下舍入。
我们有
列表 中间的元素 9 12 14 因为在第三步中,中间的元素等于目标值,所以我们可以返回该元素在列表中。
实现
二分查找既可以迭代实现,也可以实现
下面是Python中的迭代实现。
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
下面是Python中二进制搜索的递归实现。
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
二分搜索的复杂性
二分搜索的最坏情况和平均情况运行时间为
二分搜索有一个
应用程序
二分搜索是其中的一个关键思想
二分搜索可以用来帮助估计数字的平方根。通过对实现部分中所示的基本算法进行一些修改,
你如何使用二分搜索来帮助你估计一个数字的平方根?
数
的平方根 不能大于 .我们的初始搜索空间是 0,x].换句话说,“列表”是介于两者之间的一组数字 而且 . 二分搜索的基本思想是在每次迭代时将搜索空间减半。在平方根的情况下会是什么样子?我们可以选择我们的中点,就像我们在上面章节描述的算法中所做的一样。
如果中点(建议的根)不等于
的值的平方,以确定我们是应该搜索中点的左边还是右边,比较中点的值的平方和的值 .如果 中点)2小于 ,在列表的右半部分进行搜索;如果 中点)2大于 ,在列表的左半部分搜索。 要计算“第一个”和“最后一个”(或搜索空间的开始索引和搜索空间的结束索引),如果
中点)2小于 ,“first”为当前中点值,新的中点为 姓+,“last”的当前值保持“last”的值。如果 中点)2大于 ,当前的中点值成为新的“last”,“first”的当前值保持“first”的值,新的中点变为 姓+. 重复此过程,直到找到根目录。
下面是上述过程的Python实现。
12 3 4 5 6 7 8 9 10 11 12 13 |
|
另请参阅
参考文献
- , T。
二进制数组搜索 .检索自2016年5月2日https://en.wikipedia.org/wiki/File:Binary_search_into_array.png - ,。
二叉搜索 .检索于2016年4月30日http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html - ,。
二叉搜索 .检索于2016年6月5日http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html - Krenzel, S。
由二分搜索导出牛顿法 .检索自2016年5月2日http://stevekrenzel.com/articles/newtons-law