概念和记忆方法

折半的意思, 就是每次从中间对折, 记忆和实现的关键点是3个变量:
低位索引(low) , 高位索引(high), 游标(cursor). 其中游标 = low + high / 2 , 如下:

image.png

步骤图

image.png

其中第二步 c 也可能跑到右半区, 为了省事只画了左半区情况.

时间度量

第一步: n / 2 (其中n是总数)
第二步: n / 2²
第三步: n / 2³
....
可以看出用多少步能找到取决于 n 里能被2除多少次, 即一个指数方程:
n = 2^x + c , 其中多少步 = x 的值, c 是最后那一步判断的逻辑, 可以忽略不计.

两边取对数, 就有 x = \log_2n

代码

错误版本

年纪大了, 分析起来头头是道, 手写的时候发现翻车了... 怪有趣的, 一并记下.

#! /usr/bin/python
# -*- coding: UTF-8 -*-

"""

    作者: 小肥巴巴
    简书: https://www.jianshu.com/u/db796a501972
    邮箱: imyunshi@163.com
    github: https://github.com/xiaofeipapa/algo_example

    您可以任意转载, 恳请保留我作为原作者, 谢谢.

    折半查找的实现

"""


# 错误版本示例
def test_binary_search(find_data):

    data_list = [1,22,98,47,89,929,89,201,78,24,26,84,81,93,97]

    # 必须要排序
    data_list.sort()
    # print(data_list)

    step = 1
    low = 0
    high = len(data_list) - 1
    while True:

        print('-- low, high: ', low, high)
        cursor = int((low + high) / 2)
        print('---- 第%d步' % step, cursor)
        step += 1

        if data_list[cursor] == find_data:
            print('==== 找到: ', find_data)
            return

        if find_data < data_list[cursor]:
            high = cursor 
        else:
            low = cursor

if __name__ == '__main__':
    test_binary_search(84)
    test_binary_search(22)
    test_binary_search(107)

正确版本

#! /usr/bin/python
# -*- coding: UTF-8 -*-

"""

    作者: 小肥巴巴
    简书: https://www.jianshu.com/u/db796a501972
    邮箱: imyunshi@163.com
    github: https://github.com/xiaofeipapa/algo_example

    您可以任意转载, 恳请保留我作为原作者, 谢谢.

    折半查找的实现

"""


def test_binary_search(find_data):

    data_list = [1,22,98,47,89,929,89,201,78,24,26,84,81,93,97]

    # 必须要排序
    data_list.sort()
    # print(data_list)

    step = 1
    low = 0
    high = len(data_list) - 1
    while low <= high:

        print('-- low, high: ', low, high)
        cursor = int((low + high) / 2)
        print('---- 第%d步' % step, cursor)
        step += 1

        if data_list[cursor] == find_data:
            print('==== 找到: ', find_data)
            return

        if find_data < data_list[cursor]:
            high = cursor - 1
        else:
            low = cursor + 1

    print('=== 没有找到')

if __name__ == '__main__':
    test_binary_search(84)
    test_binary_search(22)
    test_binary_search(107)

关键代码对比

# 错误版本: while True
while low <= high:

if find_data < data_list[cursor]:
            # 错误版本: high = cursor
            high = cursor - 1
        else:
            # 错误版本: low = cursor
            low = cursor + 1

错误版本里, low 没有变大的机会, 循环没法终结, 因此藏着隐藏的bug: 如果到最后 data_list[0] = 20, data_list[1] = 22, 待查找数是21, 那么这个循环永远不会终结.

在正确的版本里, low 一直逼近high并最终可能超过high, 所以循环有终结的机会.

就这样, 收工.