python实现二分查找算法

yipeiwu_com5年前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将ip地址转换成整数的方法

本文实例讲述了python将ip地址转换成整数的方法。分享给大家供大家参考。具体分析如下: 有时候我们用数据库存储ip地址时可以将ip地址转换成整数存储,整数占用空间小,索引也会比较方便...

django 2.2和mysql使用的常见问题

可能是由于Django使用的MySQLdb库对Python3不支持,我们用采用了PyMySQL库来代替,导致出现各种坑,特别是执行以下2条命令的是时候: python manage....

python线程安全及多进程多线程实现方法详解

进程和线程的区别 进程是对运行时程序的封装,是系统资源调度和分配的基本单位 线程是进程的子任务,cpu调度和分配的基本单位,实现进程内并发。 一个进程可以包含多个线程,线...

python防止随意修改类属性的实现方法

如果不想允许随意修改一个类的某个属性,常用的方法是使用property装饰器以及在属性前加下划线。 class V: def __init__(self, x): se...

Python遍历zip文件输出名称时出现乱码问题的解决方法

本文实例讲述了Python遍历zip文件输出名称时出现乱码问题的解决方法。分享给大家供大家参考。具体如下: windows中使用python2.7遍历zip文件之后输出文件名等信息,co...