Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
Table of Contents
1. Cách tiếp cận vấn đề
Để hiểu về các khái niệm "xoay" của mảng input đầu vào, vui lòng đọc qua bài toán tương tự ở bài viết: 153. Find Minimum in Rotated Sorted Array , tuy nhiên điểm khác biệt ở chỗ thay vì đi tìm giá trị nhỏ nhất, bài toán yêu cầu ta trả về vị trí của phần tử target trong mảng nums (được đánh index từ 0) hoặc -1 nếu không tìm thấy. Time-Complexity được yêu cầu vẫn phải là O(logn).
Ví dụ:
- Input: nums = [4,5,6,7,0,1,2], target = 0
- Output: 4
- Explain: target = 0 nằm ở vị trí index = 4 trong mảng nums
Và tương tự với bài toán trước, ta cũng sẽ dễ dàng áp tiếp cận ngay với cách làm Binary-Search, tuy nhiên với việc target có thể linh hoạt thay đổi giá trị sẽ làm cho bài toán phức tạp hơn nhiều, đòi hỏi ta phải phân tích kỹ tất cả trường hợp có thể xảy ra để đưa ra 2 quyết định vô cùng quan trọng trong Binary-Search:
Khi nào nên tăng left? và khi nào nên giảm right?
2. Solution & Phân Tích
Ta sẽ cần xem xét tất cả trường hợp tạo nên từ vị trí của 4 giá trị: left, right, mid và target. Tuy nhiên ta sẽ chỉ quan tâm đến 3 giá trị: left, mid và target để tạo nên các điều kiện uniqe cho các trường hợp đó. Ta có thể chia làm 3 nhóm sau: (lưu ý không xét trường hợp nums[mid] = target vì hiển nhiên ta sẽ trả về kết quả là mid)
2.1. Left, Right và Mid cùng nằm trên một khoảng đơn điệu
Từ trường hợp cơ bản:
- Target nằm bên trái mid -> Cần giảm right = mid - 1 để thu hẹp khoảng tìm kiếm có chứa target về phía bên trái
- Target nằm bên phải mid -> Cần tăng left = mid + 1 để thu hẹp khoảng tìm kiếm có chứa target về phía bên phải
Nếu nums[left] <= nums[mid] < nums[right]
- Nếu nums[left] <= target < nums[mid] -> right = mid - 1
- Ngược lại -> left = mid + 1
2.2. Left và Mid cùng nằm trên một khoảng đơn điệu. Right nằm trên khoảng đơn điệu khác
Từ trường hợp cơ bản:
- Target nằm bên trái mid -> Cần giảm right = mid - 1 để thu hẹp khoảng tìm kiếm có chứa target về phía bên trái
- Target nằm bên phải mid: cả 2 trường hợp bên dưới đều cần tăng left = mid + 1 để thu hẹp khoảng tìm kiếm có chứa target về phía bên phải
- TH1
- TH2
Để thu gọn điều kiện, ta chỉ cần quan tâm trong 3 trường hợp trên, ta chỉ cần focus vô điều kiện của 1 trường hợp tăng left và giảm right, chọn điều kiện nào đơn giản hơn để làm điều kiện chính, còn cái phức tạp thì đẩy hết về else block.
Trong trường hợp này, ta thấy việc target nằm bên trái mid sẽ có điều kiện đơn giản hơn hẳn việc target nằm bên phải mid (cần chia thêm 2 trường hợp). Hay nói cách khác:
Điều kiện đơn giản là điều kiện mà target lúc này chỉ nằm trên 1 khoảng đồng biến.
Tổng kết lại, nếu nums[left] <= nums[mid] > nums[right]
- Nếu nums[left] <= target < nums[mid] -> right = mid - 1
- 2 trường hợp còn lại ta không cần quan tâm, chỉ cần biết phải tăng left = mid + 1
2.3. Right và Mid cùng nằm trên một khoảng đơn điệu. Left nằm trên khoảng đơn điệu khác
Từ trường hợp cơ bản:
Ta sẽ phát triển thêm 2 trường hợp dựa theo vị trí của target:
- Target nằm bên phải mid -> Cần tăng left = mid + 1 để thu hẹp khoảng tìm kiếm có chứa target về phía bên phải
- Target nằm bên trái mid -> cả 2 trường hợp bên dưới đều cần giảm right = mid - 1 để thu hẹp khoảng tìm kiếm có chứa target về phía bên trái
- TH1
- TH2
Về để thu gọn điều kiện, ta áp dụng nguyên tắc tương tự ở trên, tìm điều kiện mà target chỉ có thể nằm trên 1 khoảng đồng biến, và đó là khi target nằm ở bên phải mid (cần tăng left). Ta thu được:
Nếu nums[left] > nums[mid] < nums[right]
- Nếu nums[mid] < target <= nums[right] -> left = mid + 1
- 2 trường hợp còn lại ta không cần quan tâm, chỉ cần biết phải giảm right = mid - 1
2.4. Tổng hợp các điều kiện
Từ các điều kiện của 3 trường hợp:
- Nếu nums[left] <= nums[mid] < nums[right]
- Nếu nums[left] <= target < nums[mid] -> right = mid - 1
- Ngược lại -> left = mid + 1
- Nếu nums[left] <= nums[mid] > nums[right]
- Nếu nums[left] <= target < nums[mid] -> right = mid - 1
- Ngược lại -> left = mid + 1
- Nếu nums[left] > nums[mid] < nums[right]
- Nếu nums[mid] < target <= nums[right] -> left = mid + 1
- Ngược lại -> right = mid - 1
Ta sẽ tổng hợp lại được thành điều kiện sau:
- Nếu nums[left] <= nums[mid]
- Nếu nums[left] <= target < nums[mid] -> right = mid - 1
- Ngược lại -> left = mid + 1
- Ngược lại (nếu nums[left] > nums[mid])
- Nếu nums[mid] < target <= nums[right] hoặc tương đương nums[mid] < target < nums[left] -> left = mid + 1
- Ngược lại -> right = mid - 1
Explain:
- Do nums[left] <= nums[mid] đều có điểm chung nên có thể gộp lại và luôn đúng với mọi nums[right] nên điều kiện nums[right] có thể bỏ qua.
- Ở nums[left] > nums[mid] < nums[right], vế < nums[right] bị dư và có thể bỏ qua, vì khi nums[mid] đã nhỏ hơn nums[left] thì chắc chắn mid và left là 2 vị trí của 2 khoảng đồng biến riêng biệt, right lúc này chắc chắn thuộc khoảng đồng biến thứ hai cùng với mid nên chắc chắn nums[mid] luôn nhỏ hơn nums[right].
Note: Vì bài viết đã quá dài và đã cover đủ các điều kiện nên mình xin được phép không demo bằng gif để tránh phức tạp hóa thêm.
Time-Complexity: O(logn) - Use Binary Search
Space-Complexity: O(1) - In-place algorithm
n: Số lượng phần tử trong mảng nums.
3. Code
Lưu ý: Ở điều kiện else, hoàn toàn có thể thay thế if (nums[m] < target && target < nums[l]) bằng (nums[mid] < target && target <= nums[r]) với ý nghĩa tương đương như đã nêu.
