简介二分查找算法与相关的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 中,函数的定义非常简单,满足对应的语法格式要求即可。对于调用者来说,只需关注如何传递正确...

python网络编程学习笔记(八):XML生成与解析(DOM、ElementTree)

xml.dom篇     DOM是Document Object Model的简称,XML 文档的高级树型表示。该模型并非只针对 Python,而是一种普通...

Python正则表达式急速入门(小结)

Python正则表达式急速入门(小结)

正则表达式在程序开发中会经常用到,比如数据(格式)验证、替换字符内容以及提取字符串内容等等情况都会用到,但是目前许多开发人员对于正则表达式只是处于了解或者是基本会用的阶段。一旦遇到大批量...

Python ORM框架SQLAlchemy学习笔记之数据添加和事务回滚介绍

Python ORM框架SQLAlchemy学习笔记之数据添加和事务回滚介绍

1. 添加一个新对象 前面介绍了映射到实体表的映射类User,如果我们想将其持久化(Persist),那么就需要将这个由User类建立的对象实例添加到我们先前创建的Session会话实例...

Ubuntu+python将nii图像保存成png格式

这里介绍一个nii文件保存为png格式的方法。 这篇文章是介绍多个nii文件保存为png格式的方法: /post/165692.htm 系统:Ubuntu 16.04 软件: pytho...