二分查找算法的时间复杂度计算(logN)

学习笔记 马富天 2019-08-10 20:25:24 69 5

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

假设有一个递增长度为 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
  2. a = [1,2,3,4,5,6,7,8]
  3. n = 1.5
  4. def binary_search(alist,n):
  5.     
  6.     left = 0
  7.     right = len(alist) - 1
  8.     i = 1
  9.     while left <= right:
  10.         
  11.         print('第 %d 次查找' % i)
  12.         middle = left + math.floor((right - left) / 2) # 向下取整、向上取整都可以
  13.         # middle = left + math.ceil((right - left) / 2)
  14.         
  15.         if n == a[middle]:
  16.             return middle
  17.         if n < a[middle]:
  18.             right = middle - 1
  19.         else:
  20.             left = middle + 1
  21.         
  22.         i += 1
  23.         
  24.     return False
  25. binary_search(a,n)
  26. binary_search(a,2)

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

版权归 马富天个人博客 所有

本文标题:《二分查找算法的时间复杂度计算(logN)》

本文链接地址:http://www.mafutian.com/427.html

转载请务必注明出处,小生将不胜感激,谢谢! 喜欢本文或觉得本文对您有帮助,请分享给您的朋友 ^_^

1

2

上一篇《 SSH 本地端口转发和远程端口转发 》 下一篇《 字符串 "open_door" 转成 "OpenDoor","make_by_id" 转成 "MakeById" 》

所有评论

  1. 首页
  2. 上一页
  3. 1
  4. 下一页
  5. 尾页
  6. 第1页
  7. 每页12条
  8. 共1页
  9. 共5条
评论审核未开启
表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情
验证码

TOP10

  • 浏览最多
  • 评论最多