Find Minimum in Rotated Sorted Array: nửa nào được sắp xếp?

Hai bài trước trong series này có một điểm chung: search space hoàn toàn được sắp xếp. Đứng ở mid, bạn biết chắc chắn nửa nào cần loại bỏ. LeetCode 153 lấy đi điều đó. Mảng đã được sắp xếp một lần, rồi bị xoay — và chỉ thao tác đó thôi đã đủ để phá vỡ invariant làm cho vanilla binary search hoạt động.

Câu hỏi không phải là "liệu có thể dùng binary search nữa không?" Câu hỏi là "phép so sánh nào thay thế phép so sánh đã mất?"

Rotation thực sự làm gì

Lấy [0, 1, 2, 4, 5, 6, 7] và rotate bốn vị trí thành [4, 5, 6, 7, 0, 1, 2]. Mảng giờ là hai đoạn sorted nối với nhau tại một điểm giao. Mọi thứ bên trái điểm giao đều lớn hơn mọi thứ bên phải. Minimum nằm ngay đầu đoạn phải — chính tại điểm giao.

Nếu mảng bị rotate n lần (một chu kỳ đầy đủ), nó trông như bản gốc: một đoạn sorted duy nhất, minimum ở index 0. Đó là degenerate case mà thuật toán xử lý tự nhiên.

Số lần rotate không biết. Điểm rotation không biết. Phải tìm minimum mà không có thông tin đó.

Constraints ép buộc điều gì

n tối đa là 5000, nên một linear scan O(n) trên thực tế cũng sẽ pass được time limit. Nhưng đề bài yêu cầu rõ ràng O(log n). Đó là yêu cầu bắt buộc, không phải gợi ý. Khi bài toán cho bạn cấu trúc đã sorted và đòi O(log n), câu trả lời là binary search, dù cấu trúc đó bị phá vỡ một phần.

Tất cả phần tử là duy nhất. Điều này quan trọng hơn vẻ ngoài. Trong mảng rotated có duplicate, nums[mid] == nums[right] là mơ hồ — bạn không thể biết mid thuộc đoạn nào. Với phần tử duy nhất, nums[mid] luôn lớn hơn hoặc nhỏ hơn nghiêm ngặt so với nums[right], nên quyết định luôn rõ ràng. Chính constraint này mới làm cho solution O(log n) khả thi. LeetCode 154 (biến thể có duplicate) khó hơn chính vì đảm bảo này biến mất và bạn phải fallback về right -= 1 khi hai giá trị bằng nhau.

Khoảng giá trị (-5000 đến 5000) đủ hẹp để không có lo ngại arithmetic overflow trong logic so sánh — dù phép tính mid-index vẫn cần cẩn thận trong C#.

Tại sao invariant thông thường thất bại

Binary search cổ điển trên mảng sorted: nếu nums[mid] > target, target nằm bên trái; ngược lại thì bên phải. Điều đó hoạt động vì mảng tăng đơn điệu — nums[mid] đóng vai trò pivot đáng tin cậy.

Trong mảng rotated, nums[mid] có thể lớn hơn nums[right] vì hai lý do hoàn toàn khác nhau: hoặc mid rơi vào đoạn trái (segment giá trị lớn), hoặc mảng chỉ đơn giản là được sắp xếp hoàn toàn và mid đang ở đâu đó giữa chừng. Bạn không thể phân biệt hai trường hợp này bằng cách so sánh mid với left, vì left bản thân nó có thể thuộc đoạn giá trị lớn.

Đây là cái bẫy. So sánh với left thì mơ hồ. So sánh với right thì không — và lý do là cấu trúc.

Phép so sánh hoạt động được

nums[right] luôn thuộc đoạn phải (segment giá trị nhỏ). Nếu mảng được sắp xếp hoàn toàn không có rotation, nums[right] đơn giản là maximum, và minimum ở index 0 — thuật toán tìm nó bằng cách luôn đi về trái. Trong trường hợp rotated, nums[right] là giá trị lớn nhất trong đoạn phải, vẫn nhỏ hơn mọi phần tử trong đoạn trái.

Vậy decision là:

• nums[mid] > nums[right] -> mid ở đoạn trái (giá trị lớn) -> minimum nằm nghiêm ngặt bên phải mid -> left = mid + 1
• nums[mid] < nums[right] -> mid ở đoạn phải (giá trị nhỏ) -> minimum ở mid hoặc bên trái -> right = mid

Tính bất đối xứng quan trọng: ta loại trừ mid khi đi phải (left = mid + 1) nhưng giữ lại khi đi trái (right = mid). Nếu nums[mid] > nums[right], mid không thể là minimum — có gì đó bên phải nhỏ hơn. Nhưng nếu nums[mid] < nums[right], mid có thể chính là minimum.

Loop kết thúc vì mỗi lần lặp thu hẹp window nghiêm ngặt: hoặc left tăng (mid + 1 > left) hoặc right giảm (mid < right vì left < right đảm bảo mid luôn nhỏ hơn nghiêm ngặt so với right).

Approach 1: Linear scan — O(n)

Duyệt mảng, theo dõi giá trị nhỏ nhất thấy được. Đúng nhưng bỏ qua mọi thứ bài toán đảm bảo về cấu trúc.

class Solution:
    def findMin(self, nums: list[int]) -> int:
        min_val = nums[0]
        for num in nums[1:]:
            if num < min_val:
                min_val = num
        return min_val

public class Solution {
    public int FindMin(int[] nums) {
        int minVal = nums[0];
        foreach (int num in nums) {
            if (num < minVal) minVal = num;
        }
        return minVal;
    }
}

Time: O(n). Space: O(1). Không dùng binary search, không thỏa mãn ràng buộc O(log n).

Tôi sẽ không bao giờ ship cái này cho bài toán trao cho bạn cấu trúc sorted và yêu cầu O(log n). Nó hữu ích để xây dựng intuition và kiểm tra kết quả binary search trong test, nhưng không phải solution.

Approach 2: Binary search trên mảng rotated — O(log n)

Một loop, ba biến, không có auxiliary space.

class Solution:
    def findMin(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
 
        while left < right:
            mid = (left + right) // 2
 
            if nums[mid] > nums[right]:
                # mid đang ở đoạn trái (giá trị lớn); minimum nằm bên phải
                left = mid + 1
            else:
                # mid đang ở đoạn phải (giá trị nhỏ); minimum ở đây hoặc bên trái
                right = mid
 
        return nums[left]

public class Solution {
    public int FindMin(int[] nums) {
        int left = 0, right = nums.Length - 1;
 
        while (left < right) {
            int mid = left + (right - left) / 2;  // tránh int overflow
 
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
 
        return nums[left];
    }
}

Time: O(log n). Space: O(1).

Trace từng bước: [4, 5, 6, 7, 0, 1, 2]

Ba phép so sánh cho mảng 7 phần tử. Search space thu hẹp: 7 -> 3 -> 2 -> 1.

Ví dụ thứ hai, [3, 4, 5, 1, 2]:

Tại sao điều kiện loop quan trọng

Dùng while left < right với right = mid không phải ngẫu nhiên. Hai lỗi phổ biến:

while left <= right với right = mid - 1: khi minimum chính xác nằm ở mid, update right = mid - 1 sẽ vượt qua nó. Bạn trả về nums[left] nhưng left lúc này đã lệch một bước.

right = mid - 1 với left < right: vấn đề tương tự. Mid có thể là đáp án; phải giữ nó trong window.

Cặp (left < right, right = mid) đảm bảo khi loop kết thúc, left == right và index đó chính là minimum. Đây là cặp khớp nhau — phá vỡ một nửa thì logic sụp đổ.

Tính mid = left + (right - left) / 2 thay vì (left + right) / 2 tránh integer overflow khi cả hai pointer gần INT_MAX. Python không overflow, nhưng trong C# int là 32-bit và tổng có thể overflow nếu cả hai giá trị vượt khoảng 1 tỷ. Với bài này (n <= 5000), overflow không xảy ra, nhưng form an toàn không tốn thêm gì và là thói quen đúng.

Edge cases

[1] — một phần tử. left == right ngay từ đầu, body của loop không bao giờ chạy, trả về nums[0] = 1. Thuật toán degenerate gracefully.

[1, 2, 3, 4, 5] — không rotate (hoặc rotate n lần, cùng kết quả). Mỗi bước nums[mid] < nums[right] vì mảng tăng đơn điệu, nên right cứ thu nhỏ về bên trái. Hội tụ về index 0. "Rotation point" ở index 0, thuật toán tìm nó không cần special case nào.

[2, 1] — hai phần tử, rotate một lần. mid = 0, nums[0] = 2 > nums[1] = 1, nên left = 1. Trả về nums[1] = 1. Case nhỏ nhất không-tầm-thường, xử lý đúng.

[2, 3, 4, 5, 1] — minimum ở vị trí cuối. Mọi mid rơi vào indices 0–3 đều thỏa nums[mid] > nums[right], nên left tiến về bên phải cho đến khi đến index 4. Invariant nums[right] luôn thuộc đoạn phải (ở đây chỉ là index 4) giữ vững suốt.

[5, 1, 2, 3, 4] — minimum gần đầu mảng. mid rơi vào index 2 (giá trị 2), nums[right] = 4, nên right = 2. Rồi mid = 0 (giá trị 5), nums[right] = 2, left = 1. left == right = 1, trả về nums[1] = 1. Hai bước.

So sánh các approaches

Với n = 5000, linear scan làm 5000 phép so sánh. Binary search tối đa 13 (log₂(5000) ≈ 12.3). Chênh lệch không quan trọng ở quy mô này — nhưng binary search là cái scale lên n = 10⁸ mà không cần thay một dòng code nào.

Mental model cơ bản

Pattern của bài này là "modified binary search trên cấu trúc partially sorted." Insight cốt lõi: dù toàn mảng không monotonic, bạn luôn có thể tìm một sub-structure là monotonic. Ở đây, so sánh nums[mid] với nums[right] cho bạn biết mid thuộc đoạn sorted nào — và thế là đủ để halve search space.

Phép so sánh tương tự (nums[mid] vs nums[right]) xuất hiện lại trong LeetCode 33 và 81 với thêm một nhánh: sau khi biết mid thuộc đoạn nào, bạn kiểm tra thêm xem target có nằm trong đoạn đó không. Bài này là nền tảng; nắm chắc quyết định "tôi đang ở đoạn nào?" thì các biến thể khó hơn sẽ đến tự nhiên.

Từ khóa nhận diện pattern: "rotated sorted array," "find minimum," "find target in rotated," O(log n) với dữ liệu không sorted hoàn toàn.

Vị trí trong series

Hai bài đầu trong series dùng binary search trên search space được sắp xếp hoàn toàn. Bài này dùng binary search trên space được sắp xếp thành hai đoạn — và thay đổi cấu trúc duy nhất là một phép so sánh. Skeleton không đổi; invariant bạn chọn quyết định tất cả.

Tiếp theo: Search in Rotated Sorted Array (LeetCode 33), áp dụng cùng logic "đoạn nào?" để tìm một giá trị target cụ thể. Xử lý rotation giống hệt ở đây; cái thay đổi là quyết định thứ hai sau khi biết mid thuộc đoạn nào.

Bài tương tự

• LeetCode 33 — Search in Rotated Sorted Array: cùng rotation, nhưng tìm giá trị target thay vì minimum. Cùng logic nums[mid] vs nums[right], thêm một nhánh để kiểm tra target có trong đoạn vừa xác định không.
• LeetCode 81 — Search in Rotated Sorted Array II: như 33 nhưng có duplicate. Khi nums[mid] == nums[right], run membership mơ hồ — fallback right -= 1 và chấp nhận O(n) worst case.
• LeetCode 154 — Find Minimum in Rotated Sorted Array II: bài này có duplicate. Cùng degradation như 81 khi mid và right bằng nhau.
• LeetCode 162 — Find Peak Element: bài "broken monotonicity" khác, dùng logic tương tự so sánh nums[mid] với phần tử lân cận để quyết định phía nào có peak.