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

Interpolation Search là một thuật toán tìm kiếm có hiệu suất cao hơn so với tìm kiếm nhị phân trong một số trường hợp nhất định. Nó được thiết kế để tìm kiếm một phần tử cụ thể trong một mảng đã được sắp xếp theo thứ tự tăng dần. Bài viết này sẽ hướng dẫn bạn cài đặt thuật toán Interpolation Search trong lập trình một cách chi tiết.

Tổng quan về thuật toán Interpolation Search

Thuật toán Interpolation Search hoạt động dựa trên nguyên lý nội suy tuyến tính (linear interpolation). Thay vì chia đôi khoảng cách như tìm kiếm nhị phân, Interpolation Search ước lượng vị trí của khóa cần tìm dựa trên giá trị của nó so với các phần tử đầu và cuối của mảng.

Công thức tính vị trí ước lượng:

Với một mảng đã sắp xếp A có các phần tử từ lo đến hi, vị trí ước lượng pos của phần tử x được xác định như sau:

[ \text{pos} = \text{lo} + \left( \frac{(x - A[\text{lo}]) (hi - lo)}{A[\text{hi}] - A[\text{lo}]} \right) ]

Các bước cài đặt thuật toán Interpolation Search

1. Khởi tạo giá trị lo và hi cho vùng tìm kiếm:

   • lo được khởi tạo là chỉ số đầu tiên của mảng (0).
   • hi được khởi tạo là chỉ số cuối cùng của mảng (n-1).

2. Kiểm tra điều kiện dừng:

   • Nếu giá trị tại lo lớn hơn giá trị khóa cần tìm hoặc giá trị tại hi nhỏ hơn giá trị khóa cần tìm, kết thúc tìm kiếm vì phần tử không tồn tại trong mảng.

3. Tính toán vị trí dự đoán pos:

   • Sử dụng công thức trên để xác định pos.

4. Kiểm tra giá trị tại vị trí pos:

   • Nếu giá trị tại pos bằng khóa cần tìm, trả về pos.
   • Nếu giá trị tại pos nhỏ hơn khóa cần tìm, cập nhật lo bằng pos + 1.
   • Nếu giá trị tại pos lớn hơn khóa cần tìm, cập nhật hi bằng pos - 1.

5. Lặp lại quá trình cho đến khi tìm thấy phần tử cần tìm hoặc vùng tìm kiếm trở nên vô hiệu.

Cài đặt thuật toán trong Python

Dưới đây là mã nguồn cài đặt thuật toán Interpolation Search bằng Python:

def interpolation_search(arr, x):
    lo = 0
    hi = len(arr) - 1

    while lo <= hi and arr[lo] <= x <= arr[hi]:
        # Trường hợp mảng có kích thước bằng 0
        if lo == hi:
            if arr[lo] == x:
                return lo
            return -1

        # Tránh chia cho zero
        if arr[lo] == arr[hi]:
            return -1

        # Công thức nội suy tuyến tính để tìm vị trí
        pos = lo + ((x - arr[lo]) * (hi - lo) // (arr[hi] - arr[lo]))

        # Kiểm tra giá trị tại pos
        if arr[pos] == x:
            return pos

        if arr[pos] < x:
            lo = pos + 1
        else:
            hi = pos - 1

    return -1

# Ví dụ sử dụng
arr = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47]
x = 18
index = interpolation_search(arr, x)

if index != -1:
    print(f"Phần tử {x} được tìm thấy tại vị trí {index}.")
else:
    print(f"Phần tử {x} không tồn tại trong mảng.")

Kết luận

Thuật toán Interpolation Search đặc biệt hiệu quả khi các phần tử trong mảng có sự phân bố đều đặn. Trong nhiều trường hợp, nó có thể cung cấp thời gian tìm kiếm nhanh hơn đáng kể so với thuật toán tìm kiếm nhị phân. Tuy nhiên, trong trường hợp mảng có sự phân bố không đều, hiệu suất của nó có thể không được tối ưu.

Việc cài đặt và sử dụng thành thạo Interpolation Search giúp nâng cao hiệu quả tìm kiếm trong lập trình và là một bổ sung hữu ích cho bộ công cụ lập trình của bạn.