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实现二分查找算法请关注haodaima.com其它相关文章!

您可能有感兴趣的文章
Python自动化运维-使用Python脚本监控华为AR路由器关键路由变化

Python自动化运维-netmiko模块设备自动发现

Python自动化运维—netmiko模块连接并配置华为交换机

Python自动化运维-利用Python-netmiko模块备份设备配置

Python自动化运维-Paramiko模块和堡垒机实战