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 (Interpolation Search), nhóm Tìm kiếm.

Mã Python

def interpolation_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi and a[lo] <= target <= a[hi]:
        if lo == hi:
            return lo if a[lo] == target else -1
        mid = lo + (target - a[lo]) * (hi - lo) // (a[hi] - a[lo])
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

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