python实现二分查找算法

yipeiwu_com6年前Python基础

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

优点:效率高,时间复杂度为O(logN);
缺点:数据要是有序的,顺序存储。

python的代码实现如下:

#!/usr/bin/python env
# -*- coding:utf-8 -*-

def half_search(array,target):
  low = 0
  high = len(array) - 1
  while low < high:
     mid = (low + high)/2
     if array[mid] > target:
      high = mid - 1
     elif array[mid] < target:
      low = mid + 1
     elif array[mid] == target:
      print 'I find it! It is in the position of:',mid
      return mid
     else:
      print "please contact the coder!"
  return -1



if __name__ == "__main__":
  array = [1, 2, 2, 4, 4, 5]

运行结果如下:

I find it! It is in the position of: 4
4
-1
I find it! It is in the position of: 0
0
-1

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

使用python的pexpect模块,实现远程免密登录的示例

说明 当我们需要用脚本实现,远程登录或者远程操作的时候,都要去解决如何自动输入密码的问题,一般来说有3种实现方式: 1).配置公钥私钥 2).使用shell下的命令,expect 3)....

Python 一键获取百度网盘提取码的方法

Python 一键获取百度网盘提取码的方法

该 GIF 图来自于官网,文末有给出链接。 描述 依托于百度网盘巨大的的云存储空间,绝大数人会习惯性的将一些资料什么的存储到上面,但是有的私密链接需要提取码,但是让每个想下载私密资源的...

python中wx将图标显示在右下角的脚本代码

复制代码 代码如下:import wx import imagesclass DemoTaskBarIcon(wx.TaskBarIcon):    TBM...

在Python的Flask框架中使用日期和时间的教程

在Python的Flask框架中使用日期和时间的教程

 时间戳的问题 我们的微博应用的一个忽略了很久的问题就是日间和日期的显示。 直到现在,我们在我们的User和Post对象中使用Python它自己的方式来渲染时间对象,但这并不是...

python类继承用法实例分析

本文实例讲述了python类继承用法。分享给大家供大家参考。具体如下: help('object') # test class Class1(object): """ Cla...