Cài đặt thuật toán Fibonacci Search trong lập trình

Trong lĩnh vực lập trình, việc tối ưu hóa thời gian xử lý và tìm kiếm thông tin luôn là một trong những ưu tiên hàng đầu. Một trong những thuật toán nổi bật và ít được biết đến nhưng hiệu quả trong việc tìm kiếm trên các mảng đã sắp xếp là Fibonacci Search. Thuật toán này dựa trên chuỗi Fibonacci, một dãy số kỳ diệu xuất hiện rộng rãi trong tự nhiên và toán học.

Tổng Quan về Fibonacci Search

Thuật toán tìm kiếm này sử dụng các con số Fibonacci để chia mảng thành các đoạn nhỏ và dần dần thu hẹp phạm vi tìm kiếm. Mục tiêu của nó là giảm tối đa số lần so sánh để tìm ra vị trí của phần tử cần tìm kiếm. Mặc dù không phổ biến như Binary Search, nhưng nó có những ưu điểm riêng biệt trong một số trường hợp đặc biệt.

Cách Hoạt Động của Thuật Toán

Phương pháp tìm kiếm này dựa vào các bước sau:

1. Khởi tạo giá trị Fibonacci: Bắt đầu bằng việc khởi tạo ba số Fibonacci: fibM, fibM_minus_1, và fibM_minus_2. Trong đó, fibM là số Fibonacci lớn nhất nhỏ hơn hoặc bằng kích thước của mảng cần tìm kiếm.

2. Xác định phạm vi tìm kiếm: Sử dụng các giá trị Fibonacci này để xác định các vị trí kiểm tra trong mảng. Đầu tiên, chọn một chỉ số dựa trên vị trí fibM_minus_2 từ đầu mảng và so sánh giá trị tại đó với giá trị cần tìm.

3. Điều chỉnh chỉ số tìm kiếm:

   • Nếu giá trị tại chỉ số này tương đương với giá trị cần tìm, thì kết quả đã được tìm thấy.
   • Nếu nhỏ hơn, dịch chuyển phạm vi tìm kiếm xuống dưới, bỏ qua phần phía trước.
   • Nếu lớn hơn, dịch chuyển phạm vi lên trên và tiếp tục tìm kiếm.

4. Cập nhật giá trị Fibonacci: Sau mỗi lần so sánh, các giá trị fibM, fibM_minus_1, và fibM_minus_2 được cập nhật để thu hẹp phạm vi tìm kiếm theo định lý Fibonacci.

Triển Khai thuật toán trong lập trình

Dưới đây là một ví dụ về cách triển khai phương pháp tìm kiếm này bằng ngôn ngữ Python:

def fibonacci_search(arr, x):
    n = len(arr)
    
    # Initialize Fibonacci numbers
    fibM_2 = 0     # (m-2)'th Fibonacci number
    fibM_1 = 1     # (m-1)'th Fibonacci number
    fibM = fibM_2 + fibM_1     # m'th Fibonacci number
    
    # fibM is going to store the smallest Fibonacci number greater than or equal to n
    while fibM < n:
        fibM_2 = fibM_1
        fibM_1 = fibM
        fibM = fibM_2 + fibM_1
    
    # Mark the eliminated range from front
    offset = -1
    
    # while there are elements to be inspected
    while fibM > 1:
        # Check if fibM_2 is a valid location
        i = min(offset + fibM_2, n-1)
        
        # If x is greater than the value at index fibM_2, cut the subarray from offset to i
        if arr[i] < x:
            fibM = fibM_1
            fibM_1 = fibM_2
            fibM_2 = fibM - fibM_1
            offset = i
        
        # If x is less than the value at index fibM_2, cut the subarray after i+1
        elif arr[i] > x:
            fibM = fibM_2
            fibM_1 = fibM_1 - fibM_2
            fibM_2 = fibM - fibM_1
        
        # Element found. Return index
        else:
            return i
    
    # comparing the last element with x
    if fibM_1 and offset < n-1 and arr[offset + 1] == x:
        return offset + 1
    
    # element not found. Return -1
    return -1

# Example usage
arr = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100]
x = 85
index = fibonacci_search(arr, x)
print(f"Element found at index: {index}") if index != -1 else print("Element not found")

Ưu Điểm Và Nhược Điểm

Ưu Điểm:

• Hiệu quả trên các mảng đã sắp xếp.
• Đặc biệt hữu ích khi kích thước của mảng gần với một số Fibonacci.
• Giảm thiểu số lần truy cập vào phần tử của mảng.

Nhược Điểm:

• Phức tạp hơn so với các thuật toán tìm kiếm khác như Binary Search.
• Cần tính toán các số Fibonacci trước khi thực hiện tìm kiếm.

Fibonacci Search là một lựa chọn thú vị và hiệu quả đối với các mảng đã sắp xếp, đặc biệt khi bạn cần tìm kiếm nhanh và giảm thiểu số lượng phép so sánh. Dù không phải luôn luôn là lựa chọn tốt nhất, nhưng với những ứng dụng phù hợp, nó có thể mang lại hiệu quả vượt trội.