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

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

Tìm kiếm nội suy trên mảng đã sắp phân bố đều: ước lượng vị trí thăm theo GIÁ TRỊ của target thay vì luôn nhảy vào giữa như nhị phân.

Ý tưởng

Trong đoạn [lo, hi], tính vị trí dò pos = lo + ⌊(target − a[lo]) × (hi − lo) / (a[hi] − a[lo])⌋ theo nội suy tuyến tính.

a[pos] bằng target thì xong; nhỏ hơn thì thu hẹp sang phải (lo = pos + 1), lớn hơn thì thu hẹp sang trái (hi = pos − 1).

Vì sao đúng

Khi dữ liệu phân bố đều thì giá trị tỉ lệ thuận với chỉ số, nên vị trí ước lượng rất sát chỗ thật, trung bình chỉ tốn O(log log n) lần thăm.

Mã Python

def interp_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi and a[lo] <= target <= a[hi]:
        # estimate probe position by value (interpolation)
        span = (hi - lo) / (a[hi] - a[lo])
        pos = lo + int((target - a[lo]) * span)
        if a[pos] == target:
            return pos          # found
        elif a[pos] < target:
            lo = pos + 1        # narrow to the right half
        else:
            hi = pos - 1        # narrow to the left half
    return -1

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