Phỏng vấn

Tìm kiếm nhị phân trên mảng xoay (Rotated Sorted Array): Bất biến nửa đoạn tăng dần

Khi một mảng đã sắp xếp tăng dần bị cắt tại một điểm trục (pivot) và hoán đổi vị trí hai đoạn đầu cuối cho nhau, tính đơn điệu toàn cục của mảng lập tức bị phá vỡ. Đây là đề bài ưa thích trong các vòng phỏng vấn kỹ thuật vì ứng viên không thể áp dụng máy móc mẫu tìm kiếm nhị phân cơ bản mà phải phát hiện ra bất biến hình học mới của mảng xoay. Bài viết này phân tích nguyên lý "ít nhất một nửa đoạn luôn giữ nguyên thứ tự tăng dần", từ đó giải quyết trọn vẹn bài toán tìm phần tử đích, bài toán tìm giá trị nhỏ nhất trên mảng xoay trong thời gian $O(\log n)$ và cách xử lý khi mảng chứa các phần tử trùng lặp.

Ý chính
  • Bất biến cốt lõi của mảng xoay: Một mảng tăng dần gồm các phần tử phân biệt sau khi xoay chỉ có tối đa một điểm gãy (nơi phần tử đứng trước lớn hơn phần tử đứng ngay sau nó). Do đó, khi chia đoạn [l, r] tại điểm giữa mid, điểm gãy chỉ có thể rơi vào nhiều nhất một phía — phía còn lại bắt buộc phải tăng dần nghiêm ngặt.
  • Quy tắc hai bước tại mỗi vòng lặp: Bước 1: So sánh \(\text{nums}[l] \le \text{nums}[\text{mid}]\) để xác định nửa trái [l..mid] hay nửa phải [mid..r] là đoạn tăng dần liền mạch. Bước 2: Kiểm tra xem target có nằm gọn trong miền giá trị của nửa đã sắp xếp đó không để quyết định giữ hay loại nửa đó.
  • Tìm giá trị nhỏ nhất (Điểm xoay): So sánh nums[mid] với biên phải nums[r] (thay vì biên trái nums[l]) giúp phân biệt ngay mid đang nằm ở sườn cao bên trái (nums[mid] > nums[r] \(\implies l = \text{mid} + 1\)) hay sườn thấp bên phải (\(\text{nums}[\text{mid}] \le \text{nums}[r]\) \(\implies r = \text{mid}\)).
  • Trường hợp có phần tử trùng nhau: Khi nums[l] == nums[mid] == nums[r], ta không thể biết điểm gãy nằm bên nào nên phải thu hẹp hai biên l++ và r--, khiến độ phức tạp trường hợp xấu nhất chuyển về \(O(n)\).

Cấu trúc hình học của mảng xoay và bất biến chia đôi

Giả sử ban đầu ta có một mảng các số nguyên đôi một khác nhau được sắp xếp tăng dần nghiêm ngặt, chẳng hạn [0, 1, 2, 4, 5, 6, 7]. Khi xoay mảng tại điểm trục chỉ số \(4\), đoạn tiền tố [0, 1, 2] được chuyển ra phía sau đoạn hậu tố [4, 5, 6, 7], tạo thành mảng xoay:

\[\text{nums} = [4, 5, 6, 7, 0, 1, 2]\]

Nếu vẽ giá trị các phần tử lên hệ trục tọa độ, mảng xoay gồm hai sườn dốc tăng dần tách biệt:

  1. Sườn trái (Sườn cao): Gồm các phần tử [4, 5, 6, 7]. Mọi phần tử thuộc sườn trái đều lớn hơn hoặc bằng nums[0] = 4.
  2. Sườn phải (Sườn thấp): Gồm các phần tử [0, 1, 2]. Mọi phần tử thuộc sườn phải đều nhỏ hơn hoặc bằng nums[n - 1] = 2 và nhỏ hơn toàn bộ các phần tử thuộc sườn trái.

Điểm chuyển tiếp duy nhất từ 7 xuống 0 (nơi \(\text{nums}[i] \gt \text{nums}[i + 1]\)) được gọi là điểm gãy (hoặc điểm xoay). Vì toàn bộ mảng chỉ có tối đa một điểm gãy duy nhất, khi ta xét một đoạn con bất kỳ [l, r] và lấy chỉ số giữa mid = l + (r - l) / 2, điểm gãy đó không thể vừa nằm trong đoạn [l, mid] lại vừa nằm trong đoạn [mid, r]. Từ đây ta rút ra định lý nền tảng:

Tại mọi bước chia đôi đoạn [l, r] bởi điểm giữa mid, luôn có ít nhất một trong hai nửa [l..mid] hoặc [mid..r] được sắp xếp tăng dần hoàn toàn (không chứa điểm gãy).

Tìm kiếm nhị phân trên mảng xoay: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 Tại mọi bước chia đôi, luôn có ít nhất một nửa (trái hoặc phải) tăng dần nghiêm ngặt Bước 1: l = 0, r = 6 -> mid = 3 (nums[mid] = 7) [0]:4 [1]:5 [2]:6 [3]:7 [4]:0 [5]:1 [6]:2 Nửa trái [4..7] tăng dần (nums[l]=4 <= nums[mid]=7), nhưng target=0 không thuộc [4, 7) -> Bỏ nửa trái, đặt l = mid + 1 = 4 Bước 2: l = 4, r = 6 -> mid = 5 (nums[mid] = 1) -> Bước 3: l = 4, r = 4 -> Khớp tại chỉ số 4 [0]:4 [1]:5 [2]:6 [3]:7 [4]:0 [5]:1 [6]:2 Tại [4..6], mid=5 (nums[5]=1): target=0 < 1 nên dịch r = mid - 1 = 4 -> Tìm thấy nums[4] = 0 trong O(log n)
Tìm kiếm nhị phân trên mảng xoay nums = [4, 5, 6, 7, 0, 1, 2], tìm target = 0 Bước 1: l = 0, r = 6, mid = 3 (nums[3] = 7) [4, 5, 6, 7] | [0, 1, 2] • Nửa trái [4..7] đã sắp xếp tăng dần. • target = 0 không nằm trong đoạn [4, 7). -> Thu hẹp sang nửa phải: l = mid + 1 = 4 Bước 2 & 3: Đoạn [4..6] = [0, 1, 2] • Bước 2: mid = 5 (nums[5] = 1). Vì 0 < 1 nên dịch r = mid - 1 = 4. • Bước 3: l = r = 4 -> nums[4] == 0. Trả về chỉ số 4 (Độ phức tạp O(log n))
Hình 1: Quá trình tìm kiếm nhị phân phần tử target = 0 trên mảng xoay nums = [4, 5, 6, 7, 0, 1, 2]. Ở Bước 1 (mid = 3), nửa trái [4, 5, 6, 7] tăng dần nhưng không chứa 0 nên thuật toán loại bỏ toàn bộ nửa trái và nhảy sang đoạn [4..6].

Thuật toán tìm kiếm một lượt duy nhất trong O(log n)

Trong tìm kiếm nhị phân truyền thống, ta biết cả hai nửa đều tăng dần nên chỉ cần so sánh target với nums[mid]. Trên mảng xoay, ta chỉ có thể kiểm tra chắc chắn target có thuộc một đoạn hay không nếu đoạn đó tăng dần liên tục (khi đó miền giá trị của đoạn chính là khoảng đóng từ phần tử đầu đoạn đến phần tử cuối đoạn).

Do đó, tại mỗi bước lặp khi \(l \le r\) với mid = l + (r - l) / 2:

  1. Nếu nums[mid] == target, trả về ngay chỉ số mid.
  2. Kiểm tra nửa trái có tăng dần liên tục hay không bằng điều kiện \(\text{nums}[l] \le \text{nums}[\text{mid}]\):
    • Nếu đúng (\(\text{nums}[l] \le \text{nums}[\text{mid}]\)): Nửa trái nums[l..mid] chắc chắn không chứa điểm gãy và phủ kín miền giá trị tăng dần từ nums[l] đến nums[mid].
      • Ta kiểm tra tiếp: nếu nums[l] <= target && target < nums[mid], nghĩa là target nằm gọn trong nửa trái đã sắp xếp này \(\implies\) thu hẹp biên phải r = mid - 1.
      • Ngược lại, target không thể nằm trong nửa trái \(\implies\) bỏ nửa trái, đặt l = mid + 1.
    • Nếu sai (nums[l] > nums[mid]): Điểm gãy đã rơi vào nửa trái, suy ra nửa phải nums[mid..r] bắt buộc phải tăng dần liên tục và phủ miền giá trị từ nums[mid] đến nums[r].
      • Ta kiểm tra: nếu nums[mid] < target && target <= nums[r], nghĩa là target nằm gọn trong nửa phải \(\implies\) thu hẹp biên trái l = mid + 1.
      • Ngược lại \(\implies\) bỏ nửa phải, đặt r = mid - 1.
Tình huống tại bước mid Điều kiện nhận diện Nửa tăng dần liền mạch Điều kiện để target nằm trong nửa tăng dần đó Cập nhật khi thỏa / không thỏa
mid thuộc sườn cao cùng l nums[l] <= nums[mid] Nửa trái [l..mid] nums[l] <= target && target < nums[mid] Thỏa: r = mid - 1
Không thỏa: l = mid + 1
mid đã rơi xuống sườn thấp nums[l] > nums[mid] Nửa phải [mid..r] nums[mid] < target && target <= nums[r] Thỏa: l = mid + 1
Không thỏa: r = mid - 1

Hai biến thể phỏng vấn đi kèm: Tìm cực tiểu và Phần tử trùng lặp

Biến thể 1: Tìm giá trị nhỏ nhất trên mảng xoay (LeetCode 153)

Nhiều ứng viên chọn cách giải bài tìm kiếm trên mảng xoay làm 2 pha: pha 1 tìm vị trí phần tử nhỏ nhất (chỉ số điểm xoay pivot), pha 2 chạy tìm kiếm nhị phân chuẩn trên một trong hai đoạn [0..pivot-1] hoặc [pivot..n-1]. Dù cách một lượt ở mục trên gọn hơn, bản thân bài toán tìm phần tử nhỏ nhất trên mảng xoay cũng là một câu hỏi phỏng vấn độc lập rất phổ biến.

Mẹo quan trọng nhất khi tìm phần tử nhỏ nhất trên mảng xoay là luôn so sánh nums[mid] với biên phải nums[r] (không so sánh với nums[l]):

  • Nếu nums[mid] > nums[r]: Phần tử giữa lớn hơn phần tử cuối đoạn, chứng tỏ mid đang đứng ở sườn cao bên trái còn phần tử nhỏ nhất nằm ở sườn thấp bên phải \(\implies\) chắc chắn mid không phải cực tiểu, ta gán l = mid + 1.
  • Nếu \(\text{nums}[\text{mid}] \le \text{nums}[r]\): Đoạn từ mid đến r đang tăng dần, nên mọi phần tử phía sau mid đều lớn hơn hoặc bằng nums[mid], còn bản thân nums[mid] vẫn có thể là phần tử nhỏ nhất của sườn phải \(\implies\) giữ lại mid bằng cách gán r = mid. Khi vòng lặp while (\(l \lt r\)) kết thúc tại l == r, chỉ số l chính là vị trí của phần tử nhỏ nhất.

Biến thể 2: Mảng xoay có các phần tử trùng nhau (LeetCode 81)

Khi mảng được phép có các phần tử bằng nhau (ví dụ xoay mảng [1, 0, 1, 1, 1]), điều kiện \(\text{nums}[l] \le \text{nums}[\text{mid}]\) có thể gặp điểm mù khi xảy ra đồng thời:

\[\text{nums}[l] == \text{nums}[\text{mid}] == \text{nums}[r]\]

Ví dụ với nums = [1, 0, 1, 1, 1] và nums = [1, 1, 1, 0, 1], ở cả hai mảng ta đều có nums[0] = nums[2] = nums[4] = 1. Nhìn vào ba giá trị bằng nhau này, thuật toán không thể phân biệt số 0 đang ẩn ở nửa trái hay nửa phải. Giải pháp chuẩn là thêm một nhánh kiểm tra trước tiên: nếu nums[l] == nums[mid] && nums[mid] == nums[r] (mà chưa bằng target), ta loại bỏ hai đầu mút trùng lặp bằng cách tăng l++ và giảm r-- rồi lặp tiếp. Trong trường hợp trung bình độ phức tạp vẫn là \(O(\log n)\), nhưng trường hợp xấu nhất khi toàn bộ mảng bằng nhau trừ một phần tử (như [1, 1, ..., 1, 0, 1]) sẽ cần \(O(n)\) bước.

Ví dụ chạy tay từng bước

Ta chạy tay thuật toán tìm kiếm trên mảng nums = [4, 5, 6, 7, 0, 1, 2] (\(n = 7\)) với hai truy vấn: truy vấn 1 tìm target = 0 (có trong mảng tại chỉ số \(4\)) và truy vấn 2 tìm target = 3 (không có trong mảng, trả về \(-1\)).

Truy vấn Bước [l, r] mid nums[l], nums[mid], nums[r] Kiểm tra nửa tăng dần Kiểm tra miền chứa target Cập nhật [l, r]
target = 0 1 [0, 6] 3 4, 7, 2 4 <= 7 (Nửa trái [0..3] tăng) 0 thuộc [4, 7)? Sai l = mid + 1 = 4
target = 0 2 [4, 6] 5 0, 1, 2 0 <= 1 (Nửa trái [4..5] tăng) 0 thuộc [0, 1)? Đúng r = mid - 1 = 4
target = 0 3 [4, 4] 4 0, 0, 0 nums[4] == 0 == target Khớp hoàn toàn Trả về 4
target = 3 1 [0, 6] 3 4, 7, 2 4 <= 7 (Nửa trái [0..3] tăng) 3 thuộc [4, 7)? Sai l = mid + 1 = 4
target = 3 2 [4, 6] 5 0, 1, 2 0 <= 1 (Nửa trái [4..5] tăng) 3 thuộc [0, 1)? Sai l = mid + 1 = 6
target = 3 3 [6, 6] 6 2, 2, 2 2 <= 2 (Nửa trái [6..6] tăng) 3 thuộc [2, 2)? Sai l = 7 > r = 6 (\(\to\) -1)

Cài đặt bằng C++17, Python và Java 21

Chương trình dưới đây cài đặt hàm search_rotated tìm vị trí của target trong thời gian \(O(\log n)\) và bộ nhớ phụ \(O(1)\), cùng hàm find_min_rotated tìm vị trí phần tử nhỏ nhất theo Biến thể 1. Chương trình đọc n, target rồi n phần tử từ luồng vào chuẩn (hoặc tìm target = 0 trên mảng mẫu [4, 5, 6, 7, 0, 1, 2] nếu đầu vào rỗng), rồi in vị trí của target (-1 nếu không có) và giá trị nhỏ nhất của mảng. Code giả định các phần tử đôi một khác nhau như đề LeetCode 33 và 153. Với mảng có phần tử trùng (LeetCode 81), cần thêm nhánh l++, r-- của Biến thể 2 vào search_rotated, và thêm nhánh r-- khi nums[mid] == nums[r] vào hàm tìm cực tiểu.

#include <iostream>
#include <vector>
using namespace std;

int find_min_rotated(const vector<long long>& a) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[hi]) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int search_rotated(const vector<long long>& a, long long target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[lo] <= a[mid]) {
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long target;
    if (!(cin >> n >> target)) {
        vector<long long> a = {4, 5, 6, 7, 0, 1, 2};
        cout << search_rotated(a, 0) << " " << a[find_min_rotated(a)] << "\n";
        return 0;
    }
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << search_rotated(a, target) << " " << a[find_min_rotated(a)] << "\n";
    return 0;
}

Các lỗi sai kinh điển và cách tự kiểm chứng

  1. Viết thiếu dấu bằng trong điều kiện \(\text{nums}[l] \le \text{nums}[\text{mid}]\): Đây là lỗi phổ biến nhất khiến ứng viên bị sai trên các mảng chỉ còn \(2\) phần tử! Khi r = l + 1, phép chia nguyên mid = l + (r - l) / 2 sẽ cho mid == l, kéo theo nums[l] == nums[mid]. Nếu bạn viết if (nums[l] < nums[mid]) (thiếu dấu bằng), chương trình sẽ tưởng nhầm nửa trái không tăng dần và nhảy sang nhánh else kiểm tra nửa phải nums[mid] < target && target <= nums[r]. Nếu lúc đó target == nums[r], điều kiện nums[mid] < target sai (vì nums[mid] = nums[l] > nums[r]), chương trình gán r = mid - 1 và bỏ mất đáp án: với nums = [3, 1], target = 1, bản thiếu dấu bằng trả về -1 thay vì 1. Luôn viết \(\text{nums}[l] \le \text{nums}[\text{mid}]\) để xử lý đúng trường hợp mid trùng với l.
  2. So sánh nums[mid] với nums[l] khi tìm phần tử nhỏ nhất: Trong bài tìm cực tiểu, nếu bạn so sánh nums[mid] >= nums[l] và thấy đúng, bạn vẫn không biết mảng con [l..r] đang có hai sườn dốc (cực tiểu nằm bên phải mid) hay toàn bộ đoạn [l..r] đã được sắp xếp tăng dần hoàn toàn (cực tiểu chính là nums[l] ở bên trái mid)! Ngược lại, so sánh nums[mid] với nums[r] không bao giờ bị nhập nhằng vì phần tử nhỏ nhất của một đoạn tăng dần luôn nằm ở đầu trái chứ không nằm ở đầu phải.
  3. Cách tự kiểm chứng tại nhà: Với một mảng tăng dần có kích thước nhỏ \(n \in [1, 10]\), bạn có thể dùng vòng lặp sinh tất cả \(n\) phép xoay vòng có thể của mảng đó, sau đó thử tìm kiếm mọi giá trị có trong mảng lẫn các giá trị nằm xen kẽ bên ngoài mảng, rồi so sánh chỉ số trả về với hàm tìm kiếm tuần tự std::find. Cách thử vét cạn mọi điểm xoay này sẽ bắt được ngay lập tức các lỗi sai dấu \(\lt\) hoặc \(\le\) ở biên.

Luyện ngay trên Big-O Coding

Để làm chủ hoàn toàn kỹ thuật chia đôi trên mảng xoay và ma trận sắp xếp, bạn hãy luyện tập ngay bộ ba bài toán tìm kiếm nhị phân cốt lõi trong lộ trình Coding Interview 150:

Làm thế nào để biết mảng đã bị xoay sang phải bao nhiêu bước?

Số bước mà một mảng tăng dần gồm các phần tử phân biệt đã bị xoay sang phải bằng đúng chỉ số idx của phần tử nhỏ nhất trong mảng sau khi xoay. Ví dụ mảng gốc [0, 1, 2, 4, 5, 6, 7] sau khi xoay \(4\) bước sang phải thành [4, 5, 6, 7, 0, 1, 2], phần tử nhỏ nhất 0 nằm ở chỉ số idx = 4. Do đó, chỉ cần chạy thuật toán tìm chỉ số cực tiểu trên mảng xoay trong \(O(\log n)\) là bạn có ngay số bước xoay.

Giữa cách giải 1 lượt (One-pass) và cách giải 2 lượt (Tìm điểm xoay trước rồi tìm kiếm nhị phân sau), cách nào tốt hơn trong phỏng vấn?

Cả hai cách đều có cùng độ phức tạp thời gian \(O(\log n)\) và bộ nhớ \(O(1)\). Cách 1 lượt (như cài đặt trong bài viết) chỉ cần \(\approx \log_2 n\) vòng lặp thay vì \(\approx 2 \log_2 n\) vòng lặp và chỉ cần viết một vòng lặp while duy nhất nên rất được ưa chuộng. Tuy nhiên, nếu đề bài yêu cầu thực hiện hàng nghìn truy vấn tìm kiếm target khác nhau trên cùng một mảng xoay cố định, thì cách 2 lượt lại vượt trội: bạn chỉ tốn \(O(\log n)\) một lần duy nhất ở đầu chương trình để tìm điểm xoay pivot, sau đó mọi truy vấn tiếp theo chỉ cần gọi tìm kiếm nhị phân chuẩn có hằng số cực nhỏ.

Có thể áp dụng phương pháp biến đổi mảng xoay về mảng đơn điệu bằng cách cộng/trừ vô cùng (\(\pm\infty\)) không?

Có. Một kỹ thuật thú vị khác là nhìn mảng xoay từ góc độ của target: nếu cả nums[mid] và target đều nằm ở cùng một sườn (cùng lớn hơn hoặc bằng nums[0], hoặc cùng nhỏ hơn nums[0]), ta giữ nguyên giá trị nums[mid]. Nhưng nếu chúng nằm ở hai sườn khác nhau, ta tạm coi nums[mid] bằng \(+\infty\) (nếu target ở sườn trái mà nums[mid] ở sườn phải, vì đáp án nằm bên trái mid) hoặc \(-\infty\) (nếu target ở sườn phải mà nums[mid] ở sườn trái, vì đáp án nằm bên phải mid). Khi đó mảng xoay biến thành một mảng tăng dần ảo và dùng lại nguyên xi điều kiện \(\text{val} \lt \text{target}\). Dù vậy, trong phỏng vấn trực tiếp, cách xét nửa đoạn tăng dần \(\text{nums}[l] \le \text{nums}[\text{mid}]\) vẫn rõ ràng và dễ giải thích với người phỏng vấn hơn.

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483