二分法查找-算法学习
目录
二分搜索算法
在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)[1]、对数搜索(英语:logarithmic search)[2],是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
具体实现
见GitHub版本库的二分法查找。
算法实现
该算法非常快,从已经排序好的数组查找制定的元素。
- 初始化,分别有两个指向开始的元素和结束的元素。
- 每次循环后,去掉一半的元素,同时更新对应的开始和结束的指向。
- 循环结束的条件是开始小于等于结束(默认元素是升序排列)
耗时分析
机器配置 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)} (无尾调用消除)