二分法查找

#二分查找建立在有序的前提下
 1 import time
 2 
 3 def cal_time(func):
 4     def wrapper(*args, **kwargs):
 5         t1 = time.time()
 6         result = func(*args, **kwargs)
 7         t2 = time.time()
 8         print("%s running time: %s secs." % (func.__name__, t2 - t1))
 9         return result
10 
11     return wrapper

 1 @cal_time
 2 def binary_search(li, val):
 3     left = 0
 4     right = len(li) - 1
 5     while left <= right:    # 候选区有值
 6         mid = (left + right) // 2
 7         if li[mid] == val:
 8             return mid
 9         elif li[mid] > val: # 带查找的值在mid左侧
10             right = mid - 1
11         else: # li[mid] < val 带查找的值在mid右侧
12             left = mid + 1
13     else:
14         return None