简介二分查找算法与相关的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
时间: 2015-08-25

python二分查找算法的递归实现方法

本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

Python基于二分查找实现求整数平方根的方法

本文实例讲述了Python基于二分查找实现求整数平方根的方法.分享给大家供大家参考,具体如下: x=int(raw_input('please input a int:')) if x<0: retrun -1 low=0 high=x ans=(low+high)/2.0 sign=ans while ans**2 !=x: if ans**2>x: high=ans else: low=ans ans=(low+high)/2.0 if sign==ans: break print ans

Python实现二分查找算法实例

本文实例讲述了Python实现二分查找算法的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else:

python实现二分查找算法

二分查找算法:简单的说,就是将一个数组先排序好,比如按照从小到大的顺序排列好,当给定一个数据,比如target,查找target在数组中的位置时,可以先找到数组中间的数array[middle]和target进行比较,当它比target小时,那么target一定是在数组的右边,反之,则target在数组的左边,比如它比target小,则下次就可以只比较[middle+1, end]的数,继续使用二分法,将它一分为二,直到找到target这个数返回或者数组全部遍历完成(target不在数组中) 优

Python实现二分查找与bisect模块详解

前言 其实Python 的列表(list)内部实现是一个数组,也就是一个线性表.在列表中查找元素可以使用 list.index() 方法,其时间复杂度为O(n) .对于大数据量,则可以用二分查找进行优化. 二分查找要求对象必须有序,其基本原理如下: 1.从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束: 2.如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较. 3.如果在某一步骤数组为空,则代表找不到. 二分查找也

Python二分查找详解

先来看个实例 #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else: print mid return mid print -1 return -

python 二分查找和快速排序实例详解

思想简单,细节颇多:本以为很简单的两个小程序,写起来发现bug频出,留此纪念. #usr/bin/env python def binary_search(lst,t): low=0 height=len(lst)-1 quicksort(lst,0,height) print lst while low<=height: mid = (low+height)/2 if lst[mid] == t: return lst[mid] elif lst[mid]>t: height=mid-1 e

Python操作MongoDB详解及实例

Python操作MongoDB详解及实例 由于需要在页面展示MongoDB库里的数据,所以考虑使用python操作MongoDB,PyMongo模块是Python对MongoDB操作的接口包,所以首页安装pymongo. 1.安装命令 pip install pymongo 2.查询命令: import pymongo # 创建连接 client = pymongo.MongoClient(host="10.0.2.38", port=27017) # 连接probeb库 db = c

正则表达式+Python re模块详解

正则表达式(Regluar Expressions)又称规则表达式,在代码中常简写为REs,regexes或regexp(regex patterns).它本质上是一个小巧的.高度专用的编程语言. 通过正则表达式可以对指定的文本实现 匹配测试.内容查找.内容替换.字符串分割 等功能. re模块介绍 Python中的re模块提供了一个正则表达式引擎接口,它允许我们将正则表达式编译成模式对象,然后通过这些模式对象执行模式匹配搜索和字符串分割.子串替换等操作.re模块为这些操作分别提供了模块级别的函数

Python网络编程详解

1.服务器就是一系列硬件或软件,为一个或多个客户端(服务的用户)提供所需的"服务".它存在唯一目的就是等待客户端的请求,并响应它们(提供服务),然后等待更多请求. 2.客户端/服务器架构既可以应用于计算机硬件,也可以应用于计算机软件. 3.在服务器响应客户端之前,首先会创建一个通信节点,它能够使服务器监听请求. 一.套接字:通信端点 1.套接字 套接字是计算机网络数据结构,它体现了上节中所描述的"通信端点"的概念.在任何类型的通信开始之前,网络应用程序必须创建套接字

Python 多线程实例详解

Python 多线程实例详解 多线程通常是新开一个后台线程去处理比较耗时的操作,Python做后台线程处理也是很简单的,今天从官方文档中找到了一个Demo. 实例代码: import threading, zipfile class AsyncZip(threading.Thread): def __init__(self, infile, outfile): threading.Thread.__init__(self) self.infile = infile self.outfile =

Docker 打包python的命令详解

最近用Python写了一段爬虫程序,为了隔离其运行环境,易于分发,把项目打包成Docker镜像 Dockerfile FROM python:2.7.12-alpine ADD ./src /job CMD ["python", "/job/main.py"] 构建命令 $ docker build -t job . 运行 $ docker run -d --name job job 比较简单 以上所述是小编给大家介绍的Docker 打包python的命令详解,希望

windows上安装Anaconda和python的教程详解

一提到数字图像处理编程,可能大多数人就会想到matlab,但matlab也有自身的缺点: 1.不开源,价格贵 2.软件容量大.一般3G以上,高版本甚至达5G以上. 3.只能做研究,不易转化成软件. 因此,我们这里使用Python这个脚本语言来进行数字图像处理. 要使用Python,必须先安装python,一般是2.7版本以上,不管是在windows系统,还是Linux系统,安装都是非常简单的. 要使用python进行各种开发和科学计算,还需要安装对应的包.这和matlab非常相似,只是matla

基于python爬虫数据处理(详解)

一.首先理解下面几个函数 设置变量 length()函数 char_length() replace() 函数 max() 函数 1.1.设置变量 set @变量名=值 set @address='中国-山东省-聊城市-莘县'; select @address 1.2 .length()函数 char_length()函数区别 select length('a') ,char_length('a') ,length('中') ,char_length('中') 1.3. replace() 函数