二进制查找算法的 Python 实现

参考链接： Python中的二分搜索binary search

二分查找 

二分查找又叫折半查找，二分查找应该属于减治技术的成功应用。所谓减治法，就是将原问题分解成若干个子问题后，利用了规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间的关系。  二分查找利用了记录按关键码有序的特点，其基本思想为：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半边继续查找；若给定值大于中间记录的关键码，则在中间记录右半边区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。  二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)。 

下图是二分查找的减治思想： 

如果k< rmid查找这边 如果k> rmid查找这边  例如：  在有序列表list1中[1, 3, 8, 12, 23, 31, 37, 42, 48, 58]中查找值为8的记录的。 

伪代码： 

1.low = 0; high = len(list1]-1 #设置初识查找区间

2.测试查找区间[low, high]是否存在，若不存在，则查找失败；否则

3.取中间mid=(low + high)/2；比较k与list1[mid]，有以下三种情况：

  3.1 若k<r[mid]，则high=mid-1；查找在左半区进行，转2；

  3.2 若k>r[mid]，则low=mid+1；查找在右半边区进行，转2；

  3.3 若k=r[mid]，则查找成功，返回记录在表中位置mid； 

Python实现二分查找算法，代码如下： 

#!/usr/bin/python

#coding=utf-8

#自定义函数，实现二分查找，并返回查找结果

def binary_search(find, list1) :

  low = 0

  high = len(list1)

  while low <= high :

    mid = (low + high) / 2

    if list1[mid] == find :

      return mid

    #左半边

    elif list1[mid] > find :

      high = mid -1

    #右半边

    else :

      low = mid + 1

  #未找到返回-1

  return -1

list1 = [1,2,3,7,8,9,10,5]

#进行二分查找算法前必须保证要查找的序列时有序的，这里假设是升序列表

list1.sort()

print "原有序列表为:",list1

try :

  find = int(raw_input("请输入要查找的数："))

except :

  print "请输入正整数！"

  exit()

result = binary_search(find, list1)

if result != -1 : 

  print "要找的元素%d的序号为：%d" %(find,result)

else :

  print "未找到！"