Mô phỏng thuật toán Tìm trong mảng xoay

Search in Rotated Sorted Array · Nhóm: Tìm kiếm

Tìm trong mảng đã sắp rồi bị xoay quanh một trục: nhị phân sửa đổi, mỗi bước xác định nửa nào còn thứ tự để quyết định co đoạn.

Ý tưởng

Tại mid, nếu a[lo] ≤ a[mid] thì nửa trái [lo, mid] còn thứ tự, ngược lại nửa phải [mid, hi] còn thứ tự.

Kiểm tra target có nằm trong khoảng giá trị của nửa còn thứ tự không: nếu có thì co vào nửa đó, nếu không thì nhảy sang nửa kia.

Vì sao đúng

Sau khi xoay, quanh mid luôn có ít nhất một nửa còn sắp xếp; nhờ đó mỗi bước vẫn loại được một nửa phần tử như nhị phân, tốn O(log n).

Mã Python

def search_rotated(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid              # found
        if a[lo] <= a[mid]:         # left half is sorted
            if a[lo] <= target < a[mid]:
                hi = mid - 1        # target in sorted left
            else:
                lo = mid + 1
        else:                       # right half is sorted
            if a[mid] < target <= a[hi]:
                lo = mid + 1        # target in sorted right
            else:
                hi = mid - 1
    return -1

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