Search in Rotated Sorted Array: hai nửa đã sắp xếp, một điều kiện thêm

Ở bài trước về problem 153, quan sát then chốt là: trong một mảng đã bị xoay, một trong hai nửa xung quanh mid luôn luôn được sắp xếp. Insight đó cho phép tìm điểm xoay — và do đó tìm giá trị nhỏ nhất — mà không cần duyệt tuyến tính. Problem 33 mở rộng đúng ý tưởng đó sang tìm kiếm target. Bất biến giống hệt nhau. Bạn chỉ cần thêm một điều kiện.

Bài toán

Cho một mảng đã sắp xếp tăng dần và bị xoay tại một vị trí không biết trước. Tất cả giá trị đều khác nhau. Tìm target và trả về index của nó, hoặc -1 nếu không tồn tại. Yêu cầu O(log n).

nums = [4,5,6,7,0,1,2], target = 0 -> 4.

nums = [4,5,6,7,0,1,2], target = 3 -> -1.

nums = [1], target = 0 -> -1.

Đọc kỹ constraints: 1 <= nums.length <= 5000, tất cả giá trị unique, giá trị trong [-10^4, 10^4]. Ba điều rút ra ngay. Điều kiện unique là load-bearing — thuật toán bên dưới dựa vào nó, và problem 81 cho thấy điều gì vỡ khi bỏ đi nó. Yêu cầu O(log n) loại trừ mọi thứ tuyến tính: với n tối đa 5000, đó là khoảng cách 13 iterations so với 5000. Khoảng giá trị có giới hạn nghĩa là không có nguy cơ overflow, dù vậy C# vẫn nên dùng left + (right - left) / 2 như thói quen.

"Có thể bị xoay" cũng quan trọng — một mảng không bị xoay vẫn là input hợp lệ, và thuật toán cần xử lý được mà không cần case đặc biệt.

Brute force: O(n)

Đề bài yêu cầu O(log n). Nhưng việc viết ra câu trả lời naive trước giúp rõ ràng về thứ mình đang bỏ đi.

Linear scan. Kiểm tra từng phần tử. Trả về khi tìm thấy.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

public class Solution {
    public int Search(int[] nums, int target) {
        for (int i = 0; i < nums.Length; i++)
            if (nums[i] == target) return i;
        return -1;
    }
}

Time: O(n). Space: O(1). Vượt qua tất cả test case. Không đáp ứng ràng buộc của bài toán. Mảng có tối đa 5000 phần tử — ở quy mô đó O(n) nhanh đủ trong thực tế, nhưng điểm mấu chốt là học pattern, không phải qua vòng judge.

Câu hỏi thú vị là tại sao binary search vẫn có thể hoạt động trên mảng đã bị xoay, khi tiền đề của binary search là mảng phải được sắp xếp.

Bất biến: một nửa luôn được sắp xếp

Một mảng đã bị xoay trông như thế này: [4,5,6,7,0,1,2]. Hai đoạn tăng dần nối với nhau tại một điểm. Không sắp xếp toàn cục, nhưng có cấu trúc. Cấu trúc đó đủ để binary search hoạt động — nếu bạn khai thác được nó.

Chọn bất kỳ mid nào. Chỉ có một điểm nối trong mảng. Điều đó có nghĩa chỉ một trong hai nửa xung quanh mid có thể chứa nó. Nửa kia phải sạch — không điểm nối, chỉ tăng dần. Đúng một trong [left, mid] hoặc [mid, right] được sắp xếp.

Làm thế nào để biết nửa nào? So sánh nums[left] và nums[mid].

• Nếu nums[left] <= nums[mid]: nửa trái được sắp xếp. Giá trị tăng liên tục từ left đến mid. Điểm nối, nếu có, nằm đâu đó trong nửa phải.
• Nếu nums[left] > nums[mid]: nửa trái chứa điểm nối. Giá trị giảm đâu đó giữa left và mid. Nửa phải [mid, right] là phần được sắp xếp.

Đây chính là kiểm tra tương tự từ problem 153. Sự khác biệt là bạn làm gì với thông tin đó.

Điều kiện thêm

Trong 153, biết nửa nào được sắp xếp là đủ — phần tử nhỏ nhất nằm ở đầu nửa chưa được sắp xếp, nên bạn chỉ việc đi về phía đó. Trong 33, bạn cần định vị một giá trị cụ thể. Biết nửa nào được sắp xếp cho bạn biết nơi có thể thực hiện range check đáng tin cậy.

Nếu nửa trái được sắp xếp (nums[left] <= nums[mid]):

• Target nằm trong nửa trái nếu nums[left] <= target < nums[mid]. Đi trái.
• Ngược lại, nó phải nằm ở chỗ khác. Đi phải.

Nếu nửa phải được sắp xếp:

• Target nằm trong nửa phải nếu nums[mid] < target <= nums[right]. Đi phải.
• Ngược lại, nó phải nằm ở chỗ khác. Đi trái.

Cấu trúc đối xứng. Cả hai nhánh đều theo cùng logic: xác định nửa được sắp xếp, kiểm tra target có khớp không, commit vào một phía. Khi không thể xác nhận target nằm trong nửa được sắp xếp, bạn loại trừ hoàn toàn nửa đó và chuyển sang nửa kia.

Decision tree tại mỗi bước trông như thế này:

Modified binary search: O(log n)

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1
 
        while left <= right:
            mid = (left + right) // 2
 
            if nums[mid] == target:
                return mid
 
            # Nửa trái được sắp xếp
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Nửa phải được sắp xếp
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
 
        return -1

public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
 
        while (left <= right) {
            int mid = left + (right - left) / 2;
 
            if (nums[mid] == target) return mid;
 
            // Nửa trái được sắp xếp
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            // Nửa phải được sắp xếp
            else {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
 
        return -1;
    }
}

Lưu ý phiên bản C# dùng left + (right - left) / 2 thay vì (left + right) / 2. Cả hai cho kết quả giống nhau khi left và right không âm, nhưng cách sau có thể overflow với số nguyên lớn. Thói quen tốt nên giữ dù constraints không đòi hỏi.

Theo dõi ví dụ 1: tìm thấy target

nums = [4,5,6,7,0,1,2], target = 0.

Ba vòng lặp. Điểm mấu chốt ở bước 2: range check nums[left] <= target < nums[mid] được giải đúng tại boundary. 0 <= 0 là đúng. 0 < 1 là đúng. Nếu dùng < thay vì <= ở phía trái, bạn sẽ bỏ sót các target nằm đúng tại nums[left].

Theo dõi ví dụ 2: target không tồn tại

nums = [4,5,6,7,0,1,2], target = 3.

Bước 1: left=0, right=6, mid=3. nums[mid]=7, nums[left]=4. Nửa trái được sắp xếp. 3 có trong [4,7) không? Không. Tìm phải: left=4.

Bước 2: left=4, right=6, mid=5. nums[mid]=1, nums[left]=0. Nửa trái [0,1] được sắp xếp. 3 có trong [0,1) không? Không. Tìm phải: left=6.

Bước 3: left=6, right=6, mid=6. nums[mid]=2, nums[left]=2. Nửa trái được sắp xếp (trivially, một phần tử). 3 có trong [2,2) không? Không — 3 >= 2 nhưng 3 < 2 là sai. Tìm phải: left=7.

Điều kiện vòng lặp left <= right thất bại. Trả về -1.

Edge cases

Mảng một phần tử. nums = [5], target = 5: left=0, right=0, mid=0, nums[mid] == target, trả về 0. nums = [5], target = 3: equality check thất bại, rồi nums[left] <= nums[mid] (5 <= 5), range check 5 <= 3 < 5 thất bại, left=1, vòng lặp thoát, trả về -1. Cả hai hoạt động đúng — không cần case đặc biệt.

Mảng không bị xoay. nums = [1,2,3,4,5], target = 3: vì không có điểm nối, nums[left] <= nums[mid] luôn đúng trong suốt quá trình tìm kiếm, và range check thu lại thành binary search thông thường. Trường hợp không xoay suy biến thuận lợi.

Target tại nums[left]. Range check là nums[left] <= target, không strict <. Không có <=, một target nằm đúng tại boundary trái của nửa được sắp xếp sẽ bị điều hướng sai. Đây là lỗi off-by-one phổ biến nhất trong các implementation.

Target tại nums[right]. Đối xứng, check nửa phải là target <= nums[right]. Lý do tương tự — target tại boundary phải phải được bao gồm.

Target là điểm xoay. Trong [4,5,6,7,0,1,2], target = 0 nằm tại điểm xoay (index 4). Bước 2 của trace trên cho thấy điều này đúng: 0 rơi vào nửa trái được sắp xếp [0,1) khi left=4, mid=5.

Target không có trong mảng, tất cả phần tử lớn hơn. nums = [5,6,7,1,2,3], target = 0: mọi range check đều thất bại, left và right hội tụ rồi vượt nhau, trả về -1. Các boundary conditions đảm bảo không bao giờ truy cập ngoài giới hạn.

Độ phức tạp

Mỗi vòng lặp loại bỏ một nửa window còn lại. Việc xoay không thay đổi điều đó — bạn luôn tăng left hoặc giảm right bằng cách commit vào một phía. Tốc độ giảm một nửa giống binary search tiêu chuẩn, nên cùng phân tích O(log n) áp dụng. Space là O(1): ba pointers, không có cấu trúc dữ liệu thêm.

Modified binary search là thứ tôi sẽ ship không do dự. Brute force ở đây chỉ để minh họa "không tận dụng cấu trúc đã sắp xếp" trông như thế nào — không phải ứng viên nghiêm túc cho production.

Điều gì thay đổi trong problem 81 (có duplicate)

Solution này giả sử các giá trị phân biệt. Giả sử đó là load-bearing. Khi có duplicate, nums[left] == nums[mid] trở nên mơ hồ: có thể nghĩa là nửa trái được sắp xếp, hoặc cả hai endpoint tình cờ có cùng giá trị và điểm nối nằm đâu đó giữa chúng.

Problem 81 (Search in Rotated Sorted Array II) thêm một nhánh: khi nums[left] == nums[mid] == nums[right], không thể xác định nửa nào được sắp xếp, nên tăng left và giảm right rồi thử lại. Điều này làm worst case xuống O(n) (hãy tưởng tượng mảng toàn giá trị giống nhau trừ một phần tử), nhưng average case vẫn logarithmic. Cấu trúc tổng thể không thay đổi.

Nhận diện pattern

Reach for pattern này khi bạn thấy: mảng đã sắp xếp, yêu cầu O(log n), có thể bị xoay, và giá trị phân biệt. Các trigger word là "rotated", "sorted", "search", "O(log n)". Bất kỳ hai từ nào trong số đó xuất hiện cùng nhau thường có nghĩa là modified binary search.

Rộng hơn: nếu một mảng không hoàn toàn được sắp xếp nhưng có hai đoạn tăng dần ghép lại, bạn thường có thể áp dụng binary search bằng cách hỏi "tôi đang ở đoạn nào?" ở mỗi bước. Đó là kỹ năng cốt lõi ở đây, không phải các điều kiện cụ thể của bài toán này.

Các bài liên quan

Find Minimum in Rotated Sorted Array (153) — bất biến ở đây (một nửa luôn được sắp xếp) giống hệt cái dùng trong 153. Problem 153 dùng nó để tìm minimum; problem 33 dùng nó để tìm target. Nếu 33 còn mờ, quay lại 153 trước và đảm bảo bất biến đã click.

Search in Rotated Sorted Array II (81) — cùng thuật toán với một nhánh thêm cho duplicate ở boundary. Worst case giảm xuống O(n) nhưng cấu trúc giữ nguyên.

Find First and Last Position of Element in Sorted Array (34) — binary search trên mảng đã sắp xếp hoàn toàn để tìm range thay vì một index duy nhất. Luyện tập tốt cho logic half-open interval.

Find Peak Element (162) — một trường hợp khác của modified binary search khi hướng tìm kiếm phụ thuộc vào cấu trúc cục bộ thay vì thứ tự sắp xếp toàn cục.