45fan.com - 路饭网

搜索: 您的位置主页 > 网络频道 > 阅读资讯:Python二分查找算法实例分享

Python二分查找算法实例分享

2015-09-13 18:21:37 来源:www.45fan.com 【

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


本文地址:http://www.45fan.com/a/question/20955.html
Tags: 算法 查找 简介
编辑:路饭网
关于我们 | 联系我们 | 友情链接 | 网站地图 | Sitemap | App | 返回顶部