二分法查找-算法学习

二分法查找

二分搜索算法

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

具体实现

GitHub版本库的二分法查找。

算法实现

该算法非常快,从已经排序好的数组查找制定的元素。
1. 初始化,分别有两个指向开始的元素和结束的元素。
2. 每次循环后,去掉一半的元素,同时更新对应的开始和结束的指向。
3. 循环结束的条件是开始小于等于结束(默认元素是升序排列)

耗时分析

机器配置 ThinkPad T440s CPU i5-4300U Memory 8GB
num 1000 search 2992889 cost time is 4.0531158447266E-6 s
num 10000 search 2207856 cost time is 5.9604644775391E-6 s
num 100000 search 1142758 cost time is 8.1062316894531E-6 s

算法分析

最坏时间复杂度 O(log n)}
最优时间复杂度 O(1)}
平均时间复杂度 O(log n)}
空间复杂度 迭代: O(1)}
递归: O(log n)}
(无尾调用消除)

参考链接

  1. 二分法查找
  2. 二分法查找
  3. 二分法查找 百度百科

发表评论

电子邮件地址不会被公开。 必填项已用*标注