python 二分查找算法

二分查找算法

二分查找算法也称折半查找，基本思想就是折半，和平时猜数字游戏一样，比如猜的数字时67，猜测范围是0-100，则会先猜测中间值50，结果小了，所以就会从50-100猜测，中间值为75，结果大了，又从50-75猜测中间值，一直到猜中为止。因此，二分查找有一个限制就是原先数组需要是一个有序数组。代码如下：

# -*- encoding: utf-8 -*-

import time

def cal_time(func):

def wrapper(*args, **kwargs):

t1 = time.time()

result = func(*args, **kwargs)

t2 = time.time()

print("running time is :", func.__name__, t2 - t1)

return result

return wrapper

@cal_time

def binary_search(target_list, num):

low = 0

high = len(target_list) - 1

while low <= high:

mid = (high + low) // 2

if target_list[mid] == num:

return target_list[mid]

elif target_list[mid] > num:

high = mid -1

else:

low=mid+1

return

if __name__ == "__main__":

target_list=list(range(100000000))

result = binary_search(target_list,700)

print(result)