查找算法学习之二分查找（Python版本）——BinarySearch

xiaodouya33

引用
在计算机科学中，折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

• 时间复杂度:O(logn)
  
• 空间复杂度:O(1)
  

示例：

#!/usr/bin/env python
#-*-coding:utf-8-*-
def binary_search(l,key,lo=0,hi=None):
if not hi:
hi = len(l)
while lo<hi:
mid = (lo+hi)//2
if l[mid]>key:
hi = mid-1
elif l[mid]<key:
lo = mid+1
else:
return mid
return -1
def main():
L = [1,2,3,4,5,6]
print binary_search(L,6)
if __name__=="__main__":
main()

参考资料：
http://zh.wikipedia.org/wiki/%E6%8A%98%E5%8D%8A%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95