Question

python算法：二分查找

Answer 1

二分查找： 又称折半查找 ，输入一个有序的元素列表（必须是有序的）， 将列表中间位置记录的元素与查找元素比较， 如果查找的元素包含在列表中， 则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的元素大于查找元素，则进一步查找前一子表，否则进一步查找后一子表，重复以上过程，直到找到满足条件的记录，使查找成功， 二分查找 返回其位置； 或直到子表不存在为止，此时查找不成功 ，返回None。

二分查找算法要求 ： .必须是有序列表；

二分查找算法时间复杂度： O(log n)

二分查找算法优点： 比较的次数少，查找速度快，平均性能好，占用系统内存较少。

def binary_search(list,item):

low = 0

high = len(list) - 1

while low <= high:

mid = int((low + high)/2) # 整除计算也可用 mid = (low + high)//2

guess = list[mid]

if guess == item:

return mid

if guess < item:

low = mid + 1

else:

high = mid - 1

return None

my_list = [1,3,5,6,8,7,9,12,18,45]

print (binary_search(my_list,2))

print (binary_search(my_list,12))