Mô phỏng thuật toán Tìm kiếm mũ (nhân đôi)

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

Tìm kiếm mũ trên mảng đã sắp: nhân đôi biên để khoanh nhanh vùng chứa target rồi nhị phân trong đoạn hẹp đó.

Ý tưởng

Pha 1 · xuất phát bound = 1, nhân đôi bound (1, 2, 4, 8...) tới khi a[bound] không còn nhỏ hơn target hoặc bound vượt mảng.

Pha 2 · nhị phân trong đoạn [bound/2, min(bound, n·1)], vì target chắc chắn nằm trong khung vừa khoanh.

Vì sao đúng

Sau k lần nhân đôi thì bound ≈ 2^k, nên target ở vị trí p chỉ cần khoảng log p bước để khoanh; đoạn còn lại có độ dài cỡ bound/2 nên nhị phân cũng chỉ tốn log p bước.

Mã Python

def exp_search(a, target):
    n = len(a)
    if a[0] == target:          # element at the front
        return 0
    bound = 1                   # phase 1: find range by doubling
    while bound < n and a[bound] < target:
        bound *= 2
    lo = bound // 2             # phase 2: binary search
    hi = min(bound, n - 1)
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid          # found
        if 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.