Search in Rotated Sorted Array

Q: Độ phức tạp thời gian khi tìm kiếm trong một mảng đã sắp xếp nhưng bị xoay là bao nhiêu?

Thời gian O(log n) và bộ nhớ bổ sung O(1) . Mỗi bước giữ lại một nửa phạm vi, vì vậy 5000 phần tử cần tối đa 13 bước. Tìm điểm xoay trước cũng mất thời gian O(log n) , với số bước gần gấp đôi.

Q: Thuật toán có hoạt động khi mảng chứa các phần tử trùng lặp không?

Không phải với cách viết này. Khi nums[lo] , nums[mid] và nums[hi] bằng nhau, ta không thể chứng minh nửa nào đã được sắp xếp. Cách khắc phục thường dùng là tăng lo thêm một trong trường hợp đó. Cách này vẫn đảm bảo đáp án chính xác nhưng khiến độ phức tạp trong trường hợp xấu nhất là O(n) .

Q: Bạn nên tìm điểm xoay trước hay tìm trong một lượt?

Cả hai đều chạy trong O(log n) . Tìm giá trị nhỏ nhất trước sẽ chia bài toán thành hai phép tìm kiếm nhị phân thông thường. Phép tìm kiếm một lượt giải quyết bài toán trong một vòng lặp duy nhất với ít bước hơn, và đây là phiên bản mà hầu hết người phỏng vấn mong đợi.

Trung bìnhTìm kiếm nhị phân

+10

Một danh sách số nguyên phân biệt được sắp xếp theo thứ tự tăng dần rồi xoay: một số phần tử, có thể là không phần tử nào, được lấy từ đầu danh sách và chuyển về cuối theo cùng thứ tự. Ví dụ, [2, 5, 8, 11, 15, 19, 23] sau khi xoay 4 vị trí sẽ thành [15, 19, 23, 2, 5, 8, 11]. Bạn nhận được danh sách đã xoay nums và một số nguyên target. Hãy trả về chỉ số của target trong nums, tính từ 0, hoặc -1 nếu không có, với thời gian O(log n).

Hàm

search(nums: integer-array, target: integer) → integer

numsinteger-array: danh sách số nguyên phân biệt đã được xoay
targetinteger: giá trị cần tìm
Trả vềinteger: chỉ số của target trong nums, hoặc -1 nếu không tìm thấy

Ràng buộc

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i], target ≤ 10⁴
Tất cả giá trị trong nums đều khác nhau.
nums là một danh sách tăng dần được xoay đi một số vị trí k, với 0 ≤ k < nums.length; k = 0 thì danh sách không bị xoay.

Ví dụ

Đầu vào: nums = [15, 19, 23, 2, 5, 8, 11]target = 5
Đầu ra: 4
Giải thích: Phần tử giữa đầu tiên, ở chỉ số 3, có giá trị 2, nên nửa bên phải [2, 5, 8, 11] đã được sắp xếp và có giá trị 5. Phần tử giữa tiếp theo, ở chỉ số 5, có giá trị 8; phần bên trái đã sắp xếp [5, 8] có giá trị 5, dẫn đến chỉ số 4.

Đầu vào: nums = [40, 50, 60, 70, 10, 20, 30]target = 65
Đầu ra: -1
Giải thích: 65 sẽ nằm giữa 60 và 70, nhưng không có phần tử nào chứa nó. Phần tử ở giữa đầu tiên, 70, đặt 65 vào phần bên trái đã sắp xếp [40, 50, 60, 70], rồi phạm vi thu hẹp ở đó cho đến khi rỗng.

Đầu vào: nums = [8, 13, 21, 1, 3, 5]target = 13
Đầu ra: 1
Giải thích: Phần giữa đầu tiên, chỉ số 2, chứa 21. Phần bên trái [8, 13, 21] đã được sắp xếp và 13 nằm giữa 8 và 21, nên phần bên phải bị loại bỏ. Sau đó, thuật toán tìm thấy 13 ở chỉ số 1.

Câu hỏi mở rộng

Nếu nums có thể chứa các phần tử trùng lặp, không thuật toán (algorithm) nào có thể đảm bảo O(log n). Bạn có thể chứng minh điều này bằng một danh sách các số 1 đã xoay, che giấu một số 0 duy nhất không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Một danh sách đã sắp xếp rồi xoay gồm hai đoạn đã sắp xếp: [15, 19, 23], rồi đến [2, 5, 8, 11]. So sánh target với giá trị ở giữa không còn cho bạn biết nó nằm ở phía nào. Nhưng dù bạn chia danh sách ở đâu, ít nhất một nửa vẫn được sắp xếp, và chỉ cần một phép so sánh là biết liệu target có thể nằm trong nửa đó hay không.

Quét mọi phần tử

Ý tưởng

Kiểm tra từng chỉ số và trả về chỉ số đầu tiên có giá trị bằng target, hoặc -1 sau vòng lặp. Cách này đọc mọi phần tử nên đúng với mọi danh sách. Nó bỏ qua hai đoạn đã sắp xếp: 5000 phần tử cần tối đa 5000 phép so sánh, trong khi tìm kiếm nhị phân chỉ cần 13.

Thuật toán

Với mỗi chỉ số i từ 0 đến n-1, hãy so sánh nums[i] với target.
Nếu chúng bằng nhau, hãy trả về i.
Sau vòng lặp, hãy trả về -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Tìm điểm xoay, sau đó tìm kiếm nhị phân

Ý tưởng

Lần chạy thứ hai bắt đầu từ giá trị nhỏ nhất; gọi chỉ số của nó là k. Cả nums[k..n-1] và nums[0..k-1] đều đã được sắp xếp, và mọi giá trị trong đoạn đầu đều lớn hơn mọi giá trị trong đoạn thứ hai. Khi biết k, so sánh target với nums[k] và nums[n-1] sẽ xác định đoạn cần tìm, rồi tìm kiếm nhị phân thông thường sẽ hoàn tất.

Để tìm k, hãy so sánh giá trị ở giữa với nums[hi]. Nếu nums[mid] > nums[hi], các giá trị giảm ở đâu đó sau mid, nên giá trị nhỏ nhất nằm bên phải nó. Nếu không, nums[mid..hi] tăng liên tục, không có chỗ giảm, nên giá trị nhỏ nhất nằm tại mid hoặc ở phía trước. Trong ví dụ đầu tiên, các giá trị ở giữa là 2, 19 và 23, suy ra k = 3, còn 5 nằm giữa nums[3] = 2 và nums[6] = 11. Hai lần tìm kiếm nhị phân cần khoảng 2 log2 n bước.

Thuật toán

Đặt lo = 0 và hi = n-1. Khi lo < hi, tính mid; nếu nums[mid] > nums[hi], đặt lo = mid + 1, nếu không thì đặt hi = mid.
Chỉ số cuối cùng k chứa giá trị nhỏ nhất.
Nếu nums[k] ≤ target ≤ nums[n-1], tìm kiếm nhị phân các chỉ số từ k đến n-1; nếu không, tìm kiếm từ 0 đến k-1.
Trả về chỉ số tìm được, hoặc -1 nếu phạm vi tìm kiếm trống.

def search(nums, target):
    n = len(nums)
    # 1. Find k, the index of the smallest value, where the second run starts.
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the drop is right of mid
        else:
            hi = mid      # mid is in the low run: the minimum is at mid or left of it
    k = lo
    # 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
    if nums[k] <= target <= nums[n - 1]:
        lo, hi = k, n - 1
    else:
        lo, hi = 0, k - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Một lần tìm kiếm nhị phân trên nửa đã sắp xếp

Ý tưởng

Hãy giữ đúng cam kết của tìm kiếm nhị phân: nếu target nằm trong danh sách, chỉ số của nó nằm giữa lo và hi. Các giá trị chỉ giảm một lần trong toàn bộ danh sách, vì vậy nhiều nhất chỉ một trong hai nửa quanh mid chứa điểm giảm, còn nửa kia đã được sắp xếp. Nếu nums[lo] ≤ nums[mid], nửa bên trái đã được sắp xếp; nếu không, nửa bên phải đã được sắp xếp.

Với nửa đã được sắp xếp, phép kiểm tra phạm vi ở hai đầu cho biết liệu target có thể nằm bên trong hay không, chẳng hạn nums[lo] ≤ target < nums[mid] ở nửa bên trái. Nếu có thể, hãy tìm ở đó; nếu không, target chỉ có thể nằm ở nửa còn lại. Mỗi bước thu hẹp phạm vi còn một nửa: nhiều nhất 13 bước với 5000 phần tử.

Thuật toán

Đặt lo = 0 và hi = n-1.
Khi lo ≤ hi, tính mid và trả về giá trị này nếu nums[mid] bằng target.
Nếu nums[lo] ≤ nums[mid], nửa bên trái đã được sắp xếp: đặt hi = mid - 1 khi nums[lo] ≤ target < nums[mid], nếu không thì đặt lo = mid + 1.
Nếu không, nửa bên phải đã được sắp xếp: đặt lo = mid + 1 khi nums[mid] < target ≤ nums[hi], nếu không thì đặt hi = mid - 1.
Khi vòng lặp kết thúc, trả về -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            # nums[lo..mid] is sorted: target is in it only if it fits its range
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # nums[mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Lỗi thường gặp và trường hợp biên

Viết nums[lo] < nums[mid] thay vì ≤. Khi còn lại hai phần tử, mid bằng lo, và phép kiểm tra nghiêm ngặt xem [9, 4] là nửa phải đã sắp xếp: target = 4 trả về -1.
So sánh target với nums[mid] trước. Trong ví dụ đầu tiên với target = 19, số 2 ở giữa nhỏ hơn, nên tìm kiếm chuyển sang bên phải và bỏ lỡ chỉ số 1.
Chỉ kiểm tra một đầu của nửa đã sắp xếp. Với [40, 50, 60, 70, 80, 10, 20] và target = 80, chỉ dùng target ≥ nums[lo] sẽ khiến tìm kiếm đi vào [40, 50, 60, 70].
Trong Rust, k - 1 trên usize bị tràn xuống dưới khi k = 0, tức danh sách chưa xoay. Hãy dùng các phạm vi nửa mở.
Trong Lua và R, trả về vị trí bắt đầu từ 1. Hãy trừ đi 1.

Câu hỏi thường gặp3

Độ phức tạp thời gian khi tìm kiếm trong một mảng đã sắp xếp nhưng bị xoay là bao nhiêu?

Thời gian O(log n) và bộ nhớ bổ sung O(1). Mỗi bước giữ lại một nửa phạm vi, vì vậy 5000 phần tử cần tối đa 13 bước. Tìm điểm xoay trước cũng mất thời gian O(log n), với số bước gần gấp đôi.

Thuật toán có hoạt động khi mảng chứa các phần tử trùng lặp không?

Không phải với cách viết này. Khi nums[lo], nums[mid] và nums[hi] bằng nhau, ta không thể chứng minh nửa nào đã được sắp xếp. Cách khắc phục thường dùng là tăng lo thêm một trong trường hợp đó. Cách này vẫn đảm bảo đáp án chính xác nhưng khiến độ phức tạp trong trường hợp xấu nhất là O(n).

Bạn nên tìm điểm xoay trước hay tìm trong một lượt?

Cả hai đều chạy trong O(log n). Tìm giá trị nhỏ nhất trước sẽ chia bài toán thành hai phép tìm kiếm nhị phân thông thường. Phép tìm kiếm một lượt giải quyết bài toán trong một vòng lặp duy nhất với ít bước hơn, và đây là phiên bản mà hầu hết người phỏng vấn mong đợi.

def search(nums, target):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [15, 19, 23, 2, 5, 8, 11]
target = 5

Đầu ra mong đợi

Search in Rotated Sorted Array

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Quét mọi phần tử

Tìm điểm xoay, sau đó tìm kiếm nhị phân

Một lần tìm kiếm nhị phân trên nửa đã sắp xếp

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự