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实现获取系统临时目录及临时文件的方法示例

本文实例讲述了Python实现获取系统临时目录及临时文件的方法。分享给大家供大家参考,具体如下: 在开发应用程序的过程中,会有一些临时的信息,或者不太重要的信息,会保存在一个特殊的目录下...

Python的Flask框架中Flask-Admin库的简单入门指引

Python的Flask框架中Flask-Admin库的简单入门指引

 Flask-Admin是一个功能齐全、简单易用的Flask扩展,让你可以为Flask应用程序增加管理界面。它受django-admin包的影响,但用这样一种方式实现,开发者拥...

pytorch之添加BN的实现

pytorch之添加BN的实现

pytorch之添加BN层 批标准化 模型训练并不容易,特别是一些非常复杂的模型,并不能非常好的训练得到收敛的结果,所以对数据增加一些预处理,同时使用批标准化能够得到非常好的收敛结果,这...

跟老齐学Python之通过Python连接数据库

用Python来编写网站,必须要能够通过python操作数据库,所谓操作数据库,就是通过python实现对数据的连接,以及对记录、字段的各种操作。上一讲提到的那种操作方式,是看官直接通过...

Python2与python3中 for 循环语句基础与实例分析

Python2与python3中 for 循环语句基础与实例分析

下面的代码中python2与python3的print使用区别,大家注意一下。python3需要加()才行。 语法: for循环的语法格式如下: for iterating_var...