二分查找算法的时间复杂度计算（logN）

【摘要】二分查找算法是对顺序查找算法的优化，二分查找算法的前提是数列是一个有序数列，递增或者递减，本文就回顾一下最基础的算法：二分查找算法，对于它的时间复杂度的计算进行一个温习（温故而知新）。

假设有一个递增长度为 n 数列：1,2,3,4,···,n，使用二分查找算法时，每一次查找都会排除掉 1/2 的元素（当然这里不一定是真正意义上的一半，比如 n 为偶数时），所以对于 n 个元素的情况是：

未开始二分剩余： n 个元素

第一次二分剩余： (n / 2) 个元素，取中间值，进行比较

第二次二分剩余： (n / 2 / 2) 个元素，取中间值，进行次比较

...

第 k 次二分剩余： (n / (2 ^ k)) 个元素，取中间值，进行比较

在最坏的情况下，也就是排除到只剩下最后一个元素的时候，中间值向下取整，进行比较，若值相同，则查找到；不同则未查找到，因此：

(n / (2 ^ k)) = 1 时为最坏情况，即最大查找次数（目标元素处于最边缘的情况）：logN <= k <= logN + 1，去掉常数项，所以时间复杂度是O(logN)，以下给出一个具体的小例子：

n = 8：1,2,3,4,5,6,7,8，假设查找的数是 s = 1.5，即在找不到的情况，最坏的情况：

第一次二分剩余： 4 个元素，对比值 4，1.5 < 4，在左半部分

第二次二分剩余： 2 个元素，对比值 2，1.5 < 2，在左半部分

第三次二分剩余： 1 个元素，对比值 1，1 ≠ 1.5，未查找到

一共进行了 3 个查找，k = log8 = 3，2^3 = 8。

由此，我们可以知道二分查找的最坏情况就是查找 logN 次。

以下给出一个可运行的 python 代码的二分程序：

1. import math

3. a = [1,2,3,4,5,6,7,8]

4. n = 1.5

6. def binary_search(alist,n):

8.     left = 0

9.     right = len(alist) - 1

10.     i = 1

11.     while left <= right:

13.         print('第 %d 次查找' % i)

14.         middle = left + math.floor((right - left) / 2) # 向下取整、向上取整都可以

15.         # middle = left + math.ceil((right - left) / 2)

17.         if n == a[middle]:

18.             return middle

20.         if n < a[middle]:

21.             right = middle - 1

22.         else:

23.             left = middle + 1

25.         i += 1

27.     return False

29. binary_search(a,n)

30. binary_search(a,2)

二分查找算法是比较简单的一种算法，但是一定要熟记原理，因为很有可能十个人写出来的代码，有 9 个是有 bug 的。

我要打赏