19、Python算法之二分法

Python函数 / 2020-12-05

算法,即高效解决问题的方法!比如我晚上下班回去需要煮饭炒菜煲药,如果不考虑效率问题,那么煮完饭再炒菜然后煲药也是可以的,但是这种方式明显效率低下!如何提升效率呢?先来分析一下:煮饭和煲药都是需要一定时间的,而且开火后一段时间内都不需要管理,那么我可以先煮饭、煲药,在等它们完成的这段时间内,我可以备菜并进行烹饪,这样就大大提升了效率!

二分法是一种基础算法,顾名思义,把一个整体切分成两部分来进行比较,前提是有序的数据类型!下面来一个例子吧!

假设现在有一个按照从小到大的顺序来排列的列表,我需要从中找到想要的那个数字,如何做到?

先来展示不考虑算法的做法,为了更便于理解,每一次for循环都打印一次值!

l3 = [1, 3, 6, 8, 12, 24, 37, 46, 58, 66, 71, 83, 95]
lucky_number = 95
for number in l3:
    print(number)
    if lucky_number == number:
        print('we found lucky_number:', lucky_number)
        
# 执行得到结果,可以看到,因为要取的值正好在末尾,因此要遍历整个列表!
1
3
6
8
12
24
37
46
58
66
71
83
95
we found lucky_number: 95

使用二分法思路来解决这个问题

l3 = [1, 3, 6, 8, 12, 24, 37, 46, 58, 66, 71, 83, 95]

def half_algo(lucky_number, your_list):
    print(your_list)
    middle_index = len(your_list) // 2  # 取索引的中间值
    if lucky_number > your_list[middle_index]:
        your_list = your_list[middle_index + 1:]  # 因中间的索引对应的元素已经比较过,所以索引要+1往后算,:是切片意思
        half_algo(lucky_number, your_list)  # 函数递归

    elif lucky_number < your_list[middle_index]:
        your_list = your_list[:middle_index - 1]
        half_algo(lucky_number, your_list)

    else:
        print('we found lucky_number:', lucky_number)

half_algo(95, l3)

# 执行得到结果,可以看到,仅循环了三次就取到了值!
[1, 3, 6, 8, 12, 24, 37, 46, 58, 66, 71, 83, 95]
[46, 58, 66, 71, 83, 95]
[83, 95]
we found lucky_number: 95
世间微尘里 独爱茶酒中