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

yipeiwu_com7年前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命令行下退格,删除,方向键乱码(亲测有效)

一、出现原因:readline模块没有安装 二、解决方式: # 安装readline模块 yum -y install readline-devel # 进入Python安装目录 c...

关于Python中的向量相加和numpy中的向量相加效率对比

直接使用Python来实现向量的相加 # -*-coding:utf-8-*- #向量相加 def pythonsum(n): a = range(n) b = range(n)...

python进程管理工具supervisor的安装与使用教程

前言 在一个分布式环境中,每台机器上可能需要启动和停止多个进程,使用命令行方式一个一个手动启动和停止非常麻烦,而且查看每个进程的状态也很不方便。如果有一个工具能够实现每台机器上多个进程的...

在Python中关于中文编码问题的处理建议

字符串是Python中最常用的数据类型,而且很多时候你会用到一些不属于标准ASCII字符集的字符,这时候代码就很可能抛出UnicodeDecodeError: 'ascii' codec...

Python标准库之随机数 (math包、random包)介绍

我们已经在Python运算中看到Python最基本的数学运算功能。此外,math包补充了更多的函数。当然,如果想要更加高级的数学功能,可以考虑选择标准库之外的numpy和scipy项目,...