简介二分查找算法与相关的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中使用PIL模块对图片进行高斯模糊处理的教程

在Python中使用PIL模块对图片进行高斯模糊处理的教程

从一篇文章中看到,PIL 1.1.5 已经内置了高斯模糊,但是并没有在文档中提及,而且PIL的高斯模糊中 radius 是硬编码, 虽然构造方法中有传入 radius 参数,但压根就没有...

python结合shell查询google关键词排名的实现代码

python结合shell查询google关键词排名的实现代码

最近老婆大人的公司给老婆大人安排了一个根据关键词查询google网站排名的差事。老婆大人的公司是做seo的,查询的关键词及网站特别的多,看着老婆大人这么辛苦的重复着查询工作,心疼啊。所以...

Python利用pyHook实现监听用户鼠标与键盘事件

本文以一段简单的监听鼠标、键盘事件的程序,实现获取用户的输入(比如登录某些网站的账号、密码)的功能。经测试,对于一台“裸奔”的电脑,完全能获取到用户输入的任何信息;但是如果安装了杀毒软件...

解决python中用matplotlib画多幅图时出现图形部分重叠的问题

1.解决方法:使用函数 tight_layout() 2.具体使用方法 import matplotlib.pyplot as plt fig = plt.figure()...

Python生成任意范围任意精度的随机数方法

实例如下所示: # -*- coding: utf-8 -*- import numpy as np random = np.random.RandomState(0)#Random...