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
    else:
      low=mid+1
  return -1
def quicksort( lst, left , right):
  low=left
  high=right
  key=lst[left]
  if left>=right:
    return 0
  while low<high:
    while low<high and key<lst[high]:
      high=high-1
    lst[low]=lst[high]
    while low<high and key>lst[low]:
      print lst[low]
      low=low+1
    lst[high]=lst[low]
    lst[low]=key
  quicksort( lst , left ,low-1)
  quicksort( lst , low+1 , right)
if __name__=='__main__':
  print binary_search([4,8,1,5,10,2,12,3,6,9],4)

总结

以上所述是小编给大家介绍的python 二分查找和快速排序实例详解，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

  • Python中的浮点数原理与运算分析

    本文实例讲述了Python中的浮点数原理与运算.分享给大家供大家参考,具体如下: 先看一个违反直觉的例子: >>> s = 0. >>> for i in range(10): s += .1 >>> s 0.9999999999999999 # 错误被累加 再看一个更为普遍,直接影响判断逻辑的例子: >>> from math import sqrt >>> a = sqrt(2) >>> a*a

  • python中获得当前目录和上级目录的实现方法

    获取当前文件的路径: from os import path d = path.dirname(__file__) #返回当前文件所在的目录 # __file__ 为当前文件, 若果在ide中运行此行会报错,可改为 #d = path.dirname('.') 获得某个路径的父级目录: parent_path = os.path.dirname(d) #获得d所在的目录,即d的父级目录 parent_path = os.path.dirname(parent_path) ##获得parent_p

  • 基于Python数据可视化利器Matplotlib,绘图入门篇,Pyplot详解

    基于Python数据可视化利器Matplotlib,绘图入门篇,Pyplot详解

    Pyplot matplotlib.pyplot是一个命令型函数集合,它可以让我们像使用MATLAB一样使用matplotlib.pyplot中的每一个函数都会对画布图像作出相应的改变,如创建画布.在画布中创建一个绘图区.在绘图区上画几条线.给图像添加文字说明等.下面我们就通过实例代码来领略一下他的魅力. import matplotlib.pyplot as plt plt.plot([1,2,3,4]) plt.ylabel('some numbers') plt.show() 上图是我们通

  • python出现

    python出现"IndentationError: unexpected indent"错误解决办法

    python出现"IndentationError: unexpected indent"错误解决办法 Python是一种对缩进非常敏感的语言,最常见的情况是tab和空格的混用会导致错误,或者缩进不对 如下图中的代码: 以上代码中第一次运行可以正常运行 但是第二次运行时就报错了, 原因就是第二次再e之前加了一个空格" " 解决办法只要将e之前的空格删除即可 如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

  • Python调用C# Com dll组件实战教程

    Python调用C# Com dll组件实战教程

    之前公司有套C# AES加解密方案,但是方案加密用的是Rijndael类,而非AES的四种模式(ECB.CBC.CFB.OFB,这四种用的是RijndaelManaged类),Python下Crypto库AES也只有这四种模式,进而Python下无法实现C# AES Rijndael类加密效果了. 类似于这种C# 能实现的功能而在Python下实现不了的,搜集资料有两种解决方案,第一种方式,使用IronPython 直接调用C# dll文件,教程网上很多,不在赘述了,这种方式有个缺点,用的是ir

  • python去除字符串中的换行符

    今天写这个,要用python去除字符串中的换行符并写入文件,网上查阅,就一句代码replace("\n",""),加上之后,搞了半天,还是不对. 以上是我今天遇到的问题,以下是解决方案. 本地测试是window系统,正式用的时候是unix服务器.两者对换行符具体有什么差别我也不是很清楚.于是将 字符串写入的文件用 notepad++打开,显示 行尾符(如何用notepad++显示行尾符自己百度),发现是 CR, 所以将代码改为 replace("\r&qu

  • 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

  • java算法之二分查找法的实例详解

    java算法之二分查找法的实例详解 原理 假定查找范围为一个有序数组(如升序排列),要从中查找某一元素,如果该元素在此数组中,则返回其索引,否则返回-1.通过数组长度可取出中间位置元素的索引,将其值与目标值比较,如果中间位置元素值大于目标值,则在左部分进行查找,如果中间位置值小于目标值,则在右部分进行查找,如此循环,直到结束.二分查找算法之所以快是因为它没有遍历数组的每个元素,而仅仅是查找部分元素就能找到目标或确定其不存在,当然前提是查找范围为有序数组. Java的简单实现 package me

  • Python探索之URL Dispatcher实例详解

    URL dispatcher简单点理解就是根据URL,将请求分发到相应的方法中去处理,它是对URL和View的一个映射,它的实现其实也很简单,就是一个正则匹配的过程,事先定义好正则表达式和该正则表达式对应的view方法,如果请求的URL符合这个正则表达式,那么就分发这个请求到这个view方法中. 有了这个base,我们先抛出几个问题,提前思考一下: 这个映射定义在哪里?当映射很多时,如果有效的组织? URL中的参数怎么获取,怎么传给view方法? 如何在view或者是template中反解出UR

  • python+requests+unittest API接口测试实例(详解)

    python+requests+unittest API接口测试实例(详解)

    我在网上查找了下接口测试相关的资料,大都重点是以数据驱动的形式,将用例维护在文本或表格中,而没有说明怎么样去生成想要的用例, 问题: 测试接口时,比如参数a,b,c,我要先测a参数,有(不传,为空,整形,浮点,字符串,object,过短,超长,sql注入)这些情况,其中一种情况就是一条用例,同时要保证b,c的正确,确保a的测试不受b,c参数的错误影响 解决思路: 符合接口规范的参数可以手动去填写,或者准备在代码库中.那些不符合规范的参数(不传,为空,整形,浮点,字符串,object,过短,超长,

  • python中的decimal类型转换实例详解

    [Python标准库]decimal--定点数和浮点数的数学运算 作用:使用定点数和浮点数的小数运算.         Python 版本:2.4 及以后版本 decimal 模块实现了定点和浮点算术运算符,使用的是大多数人所熟悉的模型,而不是程序员熟悉的模型,即大多数计算机硬件实现的 IEEE 浮点数运算.Decimal 实例可以准确地表示任何数,对其上取整或下取整,还可以对有效数字个数加以限制. Decimal 小数值表示为 Decimal 类的实例.构造函数取一个整数或字符串作为参数.使用

  • Python 通过URL打开图片实例详解

    Python 通过URL打开图片实例详解 不论是用OpenCV还是PIL,skimage等库,在之前做图像处理的时候,几乎都是读取本地的图片.最近尝试爬虫爬取图片,在保存之前,我希望能先快速浏览一遍图片,然后有选择性的保存.这里就需要从url读取图片了.查了很多资料,发现有这么几种方法,这里做个记录. 本文用到的图片URL如下: img_src = 'http://wx2.sinaimg.cn/mw690/ac38503ely1fesz8m0ov6j20qo140dix.jpg' 1.用Open

  • Python命令启动Web服务器实例详解

    Python命令启动Web服务器实例详解 利用Python自带的包可以建立简单的web服务器.在DOS里cd到准备做服务器根目录的路径下,输入命令: python -m Web服务器模块 [端口号,默认8000] 例如: python -m SimpleHTTPServer 8080 然后就可以在浏览器中输入 http://localhost:端口号/路径 来访问服务器资源. 例如: http://localhost:8080/index.htm(当然index.htm文件得自己创建) 其他机器

  • Python 中迭代器与生成器实例详解

    Python 中迭代器与生成器实例详解

    Python 中迭代器与生成器实例详解 本文通过针对不同应用场景及其解决方案的方式,总结了Python中迭代器与生成器的一些相关知识,具体如下: 1.手动遍历迭代器 应用场景:想遍历一个可迭代对象中的所有元素,但是不想用for循环 解决方案:使用next()函数,并捕获StopIteration异常 def manual_iter(): with open('/etc/passwd') as f: try: while True: line=next(f) if line is None: br

  • python 换位密码算法的实例详解

     python 换位密码算法的实例详解 一前言: 换位密码基本原理:先把明文按照固定长度进行分组,然后对每一组的字符进行换位操作,从而实现加密.例如,字符串"Error should never pass silently",使用秘钥1432进行加密时,首先将字符串分成若干长度为4的分组,然后对每个分组的字符进行换位,第1个和第3个字符位置不变,把第2个字符和第4个字符交换位置,得到"Eorrrs shluoden v repssa liseltny" 二 代码:

  • Python 高级专用类方法的实例详解

    Python 高级专用类方法的实例详解 除了 __getitem__ 和 __setitem__ 之外 Python 还有更多的专用函数.某些可以让你模拟出你甚至可能不知道的功能.下面的例子将展示 UserDict 一些其他专用方法. def __repr__(self): return repr(self.data) (1) def __cmp__(self, dict): (2) if isinstance(dict, UserDict): return cmp(self.data, dic

随机推荐