简介二分查找算法与相关的Python实现示例

yipeiwu_com7年前Python基础

二分查找Binary Search的思想:
以有序表表示静态查找表时,查找函数可以用二分查找来实现。
二分查找(Binary Search)的查找过程是:先确定待查记录所在的区间,然后逐步缩小区间直到找到或找不到该记录为止。
1二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n)。
假设 low 指向区间下界,high 指向区间上界,mid 指向区间的中间位置,则 mid  = (low + high) / 2;
具体过程:
1.先将关键字与 mid 指向的元素比较,如果相等则返回mid。
2.关键字小于 mid 指向的元素关键字,则在 [ low,  mid-1 ]区间中继续进行二分查找。
3.关键字大于mid 指向的元素关键字,则在[ mid +1 , high] 区间中继续进行二分查找。

用Python实现二分查找示例:

>>> def find(self, num):
  l = len(self)
  first = 0
  end = l - 1
  mid = 0
  if l == 0:
   self.insert(0,num)
   return False
  while first < end:
   mid = (first + end)/2
   if num > self[mid]:
    first = mid + 1
   elif num < self[mid]:
    end = mid - 1
   else:
    break
  if first == end:
   if self[first] > num:
    self.insert(first, num)
    return False
   elif self[first] < num:
    self.insert(first + 1, num)
    return False
   else:
    return True
  elif first > end:
   self.insert(first, num)
   return False
  else:
   return True

>>> list_d = ['a','b','c','d','e','f','d','t']
>>> value_d = 't'
>>> aa=find(list_d,value_d)
>>> aa
True
>>> value_d='ha'
>>> aa=find(list_d,value_d)
>>> aa
False

相关文章

浅谈关于Python3中venv虚拟环境

浅谈关于Python3中venv虚拟环境

Python3.3以上的版本通过venv模块原生支持虚拟环境,可以代替Python之前的virtualenv。 该venv模块提供了创建轻量级“虚拟环境”,提供与系统Python的隔离支...

Python+微信接口实现运维报警

说到运维报警,我觉得都可以写个长篇历史来详细解释了报警的前世来生,比如最早报警都是用邮件,但邮件实时性不高,比如下班回家总不能人一直盯着邮箱吧,所以邮件这种报警方式不适合用来报紧急的故障...

用Python编程实现语音控制电脑

电脑面前的你,是否也希望能让电脑听命于你?   当你累的时候,只需说一声“我累了”,电脑就会放着优雅的轻音乐来让你放松。 或许你希望你在百忙之中,能让电脑郎读最新的N...

Python的re模块正则表达式操作

这个模块提供了与 Perl 相似l的正则表达式匹配操作。Unicode字符串也同样适用。 正则表达式使用反斜杠" \ "来代表特殊形式或用作转义字符,这里跟Python的语法冲突,因此...

python numpy 部分排序 寻找最大的前几个数的方法

如下所示: import numpy as np K=4 a = np.array([0, 8, 0, 4, 5, 8, 8, 0, 4, 2]) a[np.argpartition...