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

yipeiwu_com5年前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 中,函数调用(()...

python requests 库请求带有文件参数的接口实例

python requests 库请求带有文件参数的接口实例

有些接口参数是一个文件格式,比如fiddler 抓包参数如下显示 这个接口的 form-data fiddler 显示的和不带文件参数的接口有明显区别,显示的不是简单的键值对,所以我们...

Python 随机生成中文验证码的实例代码

python代码复制代码 代码如下: # -*- coding: utf-8 -*-  import Image,ImageDraw,ImageFont &nbs...

Python学习笔记之open()函数打开文件路径报错问题

Python学习笔记之open()函数打开文件路径报错问题

要以读文件的模式打开一个文件对象,使用Python内置的open()函数,传入文件名和标示符,标示符'r'表示读。 >>> f = open('D:/test.tx...

pytorch 自定义卷积核进行卷积操作方式

pytorch 自定义卷积核进行卷积操作方式

一 卷积操作:在pytorch搭建起网络时,大家通常都使用已有的框架进行训练,在网络中使用最多就是卷积操作,最熟悉不过的就是 torch.nn.Conv2d(in_channels,...