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

yipeiwu_com6年前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中类的初始化特殊方法

什么是特殊方法?当我们在设计一个类的时候,python中有一个用于初始化的方法$__init__$,类似于java中的构造器,这个就是特殊方法,也叫作魔术方法。简单来说,特殊方法可以给你...

Python时区设置方法与pytz查询时区教程

时区的概念与转换 首先要知道时区之间的转换关系,其实这很简单:把当地时间减去当地时区,剩下的就是格林威治时间了。 例如北京时间的18:00就是18:00+08:00,相减以后就是10:0...

Python OOP类中的几种函数或方法总结

概述 实例方法 使用实例调用时,默认传递实例本身到实例方法的第一个参数self 使用类调用时,必须传递一个实例对象到实例方法的第一个参数 静态方法 使用实例调用和类调用...

浅谈python在提示符下使用open打开文件失败的原因及解决方法

浅谈python在提示符下使用open打开文件失败的原因及解决方法

题目:在提示符下使用open打开一个文件 刚开始网上看了下打开的方式,结果一直实现不了,报错是没找到这个文件,而且和我输入的文件名不一样。 错误如下: >>>ope...

python验证码识别教程之滑动验证码

前言 上篇文章记录了2种分割验证码的方法,此外还有一种叫做”滴水算法”(Drop Fall Algorithm)的方法,但本人智商原因看这个算法看的云里雾里的,所以今天记录滑动验证码的处...