简介二分查找算法与相关的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的Flask中使用WTForms表单框架的基础教程

在Python的Flask中使用WTForms表单框架的基础教程

下载和安装 安装 WTForms 最简单的方式是使用 easy_install 和 pip: easy_install WTForms # or pip install WTForm...

利用Python读取txt文档的方法讲解

利用Python读取txt文档的方法讲解

在G:/PythonPractise文件夹下新建一个名为record.txt的文本文档,写入如下图所示四行内容并保存。 打开python3的idle,开始写代码。 方法一代码和运行结果...

Python实现两款计算器功能示例

本文实例为大家分享了Python实现计算器功能示例代码,供大家参考,具体内容如下 1.简单计算器 #计算一个表达式的时候,首先肯定是先算括号里面的,再算乘除法,后算加减法 imp...

pandas中去除指定字符的实例

pandas中去除指定字符的实例

例表: 假如想要去掉表中的‘#',‘;'而且以‘#'和‘;'为分割线切割数据: #将dfxA_2的每一个分隔符之间的数据提出来 col1=dfxA_2['travel_seq']...

python实现简单名片管理系统

前言 之前看过一遍的python教程,真的是自己看过一遍,python的程序能看懂,但是很难去实现。比较困难的自己实现一些代码,找工作原因,自己又认认真真的看书,敲代码,后来看到了这个...