二分搜索算法
在计算机科学中，二分搜索（英语：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)}
（无尾调用消除）
参考链接
打赏作者
