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

更新时间：2015年08月26日 12:12:26 作者：buaa_shang

这篇文章主要介绍了二分查找算法与相关的Python实现示例,Binary Search同时也是算法学习当中最基础的知识,需要的朋友可以参考下

二分查找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 的简单栅格图像边界提取方法，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧
2019-07-07
python中wx模块的具体使用方法
这篇文章主要介绍了python中wx模块的具体使用方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
2020-05-05
浅谈Python描述数据结构之KMP篇
这篇文章主要介绍了Python描述数据结构之KMP篇，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
2020-09-09
Python 抓取微信公众号账号信息的方法
搜狗微信搜索提供两种类型的关键词搜索，一种是搜索公众号文章内容，另一种是直接搜索微信公众号。这篇文章主要介绍了Python 抓取微信公众号账号信息,需要的朋友可以参考下
2019-06-06
Python模块future用法原理详解
这篇文章主要介绍了Python模块future用法原理详解,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
2020-01-01
SpringBoot实现登录注册常见问题解决方案
这篇文章主要介绍了SpringBoot实现登录注册常见问题解决方案,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
2020-03-03
python操作excel之openpyxl模块读写xlsx格式使用方法详解
这篇文章主要介绍了python操作excel之openpyxl模块读写xlsx格式使用方法详解,需要的朋友可以参考下
2022-12-12
python3 tcp的粘包现象和解决办法解析
这篇文章主要介绍了python3 tcp的粘包现象和解决办法解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
2019-12-12
python实现requests发送/上传多个文件的示例
今天小编就为大家分享一篇python实现requests发送/上传多个文件的示例，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧
2018-06-06
python取余运算符知识点详解
在本篇文章中我们给大家整理了关于python取余运算符的写法以及相关知识点，有兴趣的朋友们可以参考学习下。
2019-06-06