- 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ữamid, đ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 xemtargetcó 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ảinums[r](thay vì biên tráinums[l]) giúp phân biệt ngaymidđ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ênl++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:
- 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ằngnums[0] = 4. - 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ằngnums[n - 1] = 2và 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ữamid, 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).
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:
- Nếu
nums[mid] == target, trả về ngay chỉ sốmid. - 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]đếnnums[mid].- Ta kiểm tra tiếp: nếu
nums[l] <= target && target < nums[mid], nghĩa làtargetnằm gọn trong nửa trái đã sắp xếp này \(\implies\) thu hẹp biên phảir = mid - 1. - Ngược lại,
targetkhông thể nằm trong nửa trái \(\implies\) bỏ nửa trái, đặtl = mid + 1.
- Ta kiểm tra tiếp: nếu
- Nếu sai (
nums[l] > nums[mid]): Điểm gãy đã rơi vào nửa trái, suy ra nửa phảinums[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]đếnnums[r].- Ta kiểm tra: nếu
nums[mid] < target && target <= nums[r], nghĩa làtargetnằm gọn trong nửa phải \(\implies\) thu hẹp biên tráil = mid + 1. - Ngược lại \(\implies\) bỏ nửa phải, đặt
r = mid - 1.
- Ta kiểm tra: nếu
- Nếu đúng (\(\text{nums}[l] \le \text{nums}[\text{mid}]\)): Nửa trái
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 - 1Khô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 + 1Khô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ắnmidkhông phải cực tiểu, ta gánl = mid + 1. - Nếu \(\text{nums}[\text{mid}] \le \text{nums}[r]\): Đoạn từ
midđếnrđang tăng dần, nên mọi phần tử phía saumidđều lớn hơn hoặc bằngnums[mid], còn bản thânnums[mid]vẫn có thể là phần tử nhỏ nhất của sườn phải \(\implies\) giữ lạimidbằng cách gánr = mid. Khi vòng lặpwhile(\(l \lt r\)) kết thúc tạil == r, chỉ sốlchí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;
}
import sys
def find_min_rotated(a: list[int]) -> int:
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] > a[hi]:
lo = mid + 1
else:
hi = mid
return lo
def search_rotated(a: list[int], target: int) -> int:
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
if a[lo] <= a[mid]:
if a[lo] <= target < a[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if a[mid] < target <= a[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
def main():
tokens = sys.stdin.read().split()
if not tokens:
a = [4, 5, 6, 7, 0, 1, 2]
print(f"{search_rotated(a, 0)} {a[find_min_rotated(a)]}")
return
n = int(tokens[0])
target = int(tokens[1])
a = [int(x) for x in tokens[2:2 + n]]
print(f"{search_rotated(a, target)} {a[find_min_rotated(a)]}")
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
public static int findMinRotated(long[] a) {
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] > a[hi]) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
public static int searchRotated(long[] a, long target) {
int lo = 0, hi = a.length - 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;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) {
long[] a = {4, 5, 6, 7, 0, 1, 2};
System.out.println(searchRotated(a, 0) + " " + a[findMinRotated(a)]);
return;
}
int n = sc.nextInt();
long target = sc.nextLong();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
System.out.println(searchRotated(a, target) + " " + a[findMinRotated(a)]);
}
}
Các lỗi sai kinh điển và cách tự kiểm chứng
- 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ênmid = l + (r - l) / 2sẽ chomid == l, kéo theonums[l] == nums[mid]. Nếu bạn viếtif (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ánhelsekiểm tra nửa phảinums[mid] < target && target <= nums[r]. Nếu lúc đótarget == nums[r], điều kiệnnums[mid] < targetsai (vìnums[mid] = nums[l] > nums[r]), chương trình gánr = mid - 1và bỏ mất đáp án: vớinums = [3, 1],target = 1, bản thiếu dấu bằng trả về-1thay vì1. Luôn viết \(\text{nums}[l] \le \text{nums}[\text{mid}]\) để xử lý đúng trường hợpmidtrùng vớil. - So sánh
nums[mid]vớinums[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ánhnums[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ảimid) 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áimid)! Ngược lại, so sánhnums[mid]vớinums[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. - 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.
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.


