折半查找和斐波那契查找的对比测试笔记

先上两者的 Python 代码。
折半查找：

def bin_search_(find_num, list_, k):
    split_pos = len(list_) // 2
    if find_num == list_[split_pos]:
        return split_pos + k
    elif len(list_) == 0:
        return None
    elif find_num < list_[split_pos]:
        return bin_search_(find_num, list_[:split_pos], k)
    else:
        return bin_search_(find_num, list_[split_pos+1:], k+split_pos+1)


def bin_search(find_num, list_):
    return bin_search_(find_num, list_, 0)


if __name__ == '__main__':
    list_ = [1, 2, 4, 5, 9, 11, 20, 33, 44, 50]
    find_num = 20
    print(bin_search(find_num, list_))

斐波那契查找：

def get_fib(list_len):
    a, b = 0, 1
    fib = []
    while True:
        fib.append(a)
        if a > list_len:
            return fib
        else:
            a, b = b, a + b


def fib_find(find_num, index, list_, fib, k):
    split_pos = fib[index-1] - 1
    if find_num == list_[split_pos]:
        return split_pos + k
    elif len(list_) == 0:
        return None
    elif find_num < list_[split_pos]:
        return fib_find(find_num, index-1, list_[:split_pos+1], fib, k)
    else:
        return fib_find(find_num, index-2, list_[split_pos+1:], fib, k+fib[index-1])


def fib_search_(find_num, list_, fib):
    list_len = len(list_)
    index, good_len = len(fib)-1, fib[-1]
    [list_.append(list_[-1]) for i in range(good_len-list_len)]
    final_index = fib_find(find_num, index, list_, fib, 0)
    [list_.pop() for i in range(good_len-list_len)]
    if final_index > list_len - 1:
        return list_len - 1
    else:
        return final_index


def fib_search(find_num, list_):
    fib = get_fib(len(list_))
    return fib_search_(find_num, list_, fib)


if __name__ == '__main__':
    list_ = [1, 2, 4, 5, 9, 11, 20, 33, 44, 50]
    find_num = 20
    print(fib_search(find_num, list_))
    find_num = 50
    print(fib_search(find_num, list_))

根据资料显示，斐波那契查找的平均效率会比折半查找更高。但在 Python 中，根据测试发现，使用斐波那契查找时，列表的 append 和 pop 操作比较消耗时间；除此之外，递归次数也比折半查找要多。
总之，在大多数时候，有序线性表查找时直接使用折半查找足以使用。