简介二分查找算法与相关的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

相关文章

解决Pytorch训练过程中loss不下降的问题

在使用Pytorch进行神经网络训练时,有时会遇到训练学习率不下降的问题。出现这种问题的可能原因有很多,包括学习率过小,数据没有进行Normalization等。不过除了这些常规的原因,...

小白入门篇使用Python搭建点击率预估模型

小白入门篇使用Python搭建点击率预估模型

点击率预估模型 0.前言 本篇是一个基础机器学习入门篇文章,帮助我们熟悉机器学习中的神经网络结构与使用。 日常中习惯于使用Python各种成熟的机器学习工具包,例如sklearn、Te...

使用Python来做一个屏幕录制工具的操作代码

使用Python来做一个屏幕录制工具的操作代码

一、写在前面 作为一名测试,有时候经常会遇到需要录屏记录自己操作,方便后续开发同学定位。以前都是用ScreenToGif来录屏制作成动态图,偶尔的机会看到python也能实现。那就赶紧...

pytorch打印网络结构的实例

pytorch打印网络结构的实例

最简单的方法当然可以直接print(net),但是这样网络比较复杂的时候效果不太好,看着比较乱;以前使用caffe的时候有一个网站可以在线生成网络框图,tensorflow可以用tens...

解决Pycharm调用Turtle时 窗口一闪而过的问题

解决Pycharm调用Turtle时 窗口一闪而过的问题

如下所示: #彩色螺旋线 import turtle turtle.pensize(2) turtle.bgcolor("black") colors = ["red","yello...