python 折半排序

#!/usr/bin/python
# 输入的列表必须是已经排好序的列表
def binary_search(li, val):
    left = 0 #定义开始范围
    right = len(li)-1  #定义查找结束范围
    while left <= right: #如果左边的值小于右边的值 证明候选区还有值 继续循环查找
        mid = (left+right) // 2 #获取候选区中间的值
        if li[mid] == val:  #如果中间值等于要查找的值 则结束算法
            print mid
            return
        elif li[mid] > val: # 如果中间的值大于要查找的值 则证明右边的范围值需要按照中间值进行折半 mid-1 是不需要和原来的中间值比较
            right = mid - 1
        else:#li[mid] < val
            left = mid+1 # 如果中间的值小于要查找的值 则证明左边的范围值需要按照中间值进行折半 mid+1 是不需要和原来的中间值比较
    else:
        print "none" # 否则就是没找到值

#时间复杂度 O(logn) 相比线性查找效率更高