简介二分查找算法与相关的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

相关文章

python模块hashlib(加密服务)知识点讲解

官方文案:https://docs.python.org/zh-cn/3/library/hashlib.html hashlib --- 安全哈希与消息摘要 Python的hashl...

对IPython交互模式下的退出方法详解

如果进入了shell交互窗口,python的退出方式只能够用函数不能够用命令,这有时候让人感觉到很不习惯。因为函数会比命令多一个括号的输入,这让人有点反感。而Linux的终端、DOS C...

简单分析Python中用fork()函数生成的子进程

python的os module中有fork()函数用于生成子进程,生成的子进程是父进程的镜像,但是它们有各自的地址空间,子进程复制一份父进程内存给自己,两个进程之 间的执行是相互独立的...

python 三元运算符使用解析

三元运算又称三目运算,是对简单的条件语句的简写 简单条件语句: if 条件成立: val = 1 else: val = 2 改成三元运算: val = 1 if 条件...

Flask框架的学习指南之用户登录管理

继续flask的学习之旅。今天介绍flask的登陆管理模块,还记得上一篇中的blog小项目么,登录是咱们自己写的验证代码,大概有以下几个步骤: 1、在登录框中输入用户名和密码 2、fla...