二分法查找-算法学习

目录

二分搜索算法

在计算机科学中，二分搜索（英语：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. 二分法查找 百度百科 img