Mô phỏng thuật toán Tìm kiếm Fibonacci

Fibonacci Search · Nhóm: Tìm kiếm

Tìm kiếm Fibonacci trên mảng đã sắp: dùng các số Fibonacci để chọn vị trí dò và chia đoạn, chỉ cần phép cộng và trừ.

Ý tưởng

Tìm số Fibonacci F nhỏ nhất không nhỏ hơn n để làm khung, đặt offset = −1 cho phần đã loại.

Mỗi bước dò tại i = min(offset + F(k·2), n·1): a[i] nhỏ hơn target thì bỏ phần đầu và dời offset, lớn hơn thì bỏ phần đuôi; tụt khung Fibonacci sau mỗi lần.

Vì sao đúng

Mỗi bước loại đi một phần đoạn theo tỉ lệ vàng của dãy Fibonacci, nên vùng xét thu nhỏ theo cấp số nhân, tổng cộng O(log n) lần dò.

Mã Python

def fib_search(a, target):
    n = len(a)
    fib2, fib1 = 0, 1            # F(k-2), F(k-1)
    fibM = fib2 + fib1          # F(k)
    while fibM < n:             # smallest Fibonacci >= n
        fib2, fib1 = fib1, fibM
        fibM = fib2 + fib1
    offset = -1                 # eliminated front
    while fibM > 1:
        i = min(offset + fib2, n - 1)   # probe index
        if a[i] < target:       # cut lower third
            fibM, fib1, fib2 = fib1, fib2, fib1 - fib2
            offset = i
        elif a[i] > target:     # cut upper third
            fibM, fib1, fib2 = fib2, fib1 - fib2, fib2 - (fib1 - fib2)
        else:
            return i            # found
    if fib1 and offset + 1 < n and a[offset + 1] == target:
        return offset + 1
    return -1

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.