33. Search in Rotated Sorted Array
Tags:
Medium
Skills:
Binary Search
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm vị trí của một phần tử target trong một mảng đã được sắp xếp tăng dần và sau đó bị rotated tại một điểm chưa biết. Mảng không chứa phần tử trùng nhau.
Yêu cầu đồ phức tạp thời gian là O(logn), tức là phải dùng biến thể của binary search
Approach
mid) của mảng.left đến mid hoặc từ mid đến right) luôn được sắp xếp tăng dần.target có nằm trong nửa đó không.Mô tả thuật toán
left = 0, right = nums.length - 1 left <= right mid = left + Math.floor((right - left) / 2) nums[mid] === target return midnums[left] -> mid được sắp xếptarget nằm trong đoạn này (nums[left] <= target < nums[mid]), cập nhật right = mid - 1.left = mid + 1.nums[mid] đến nums[right] được sắp xếp:target nằm trong đoạn này (nums[mid] < target <= nums[right]), cập nhật left = mid + 1.right = mid - 1.-1.Solution
1function search(nums: number[], target: number): number {
2 let left = 0;
3 let right = nums.length - 1;
4 while (left <= right) {
5 const mid = left + Math.floor((right - left) / 2)
6 if (nums[mid] === target) return mid
7
8 if (nums[left] <= nums[mid]) {
9 if (nums[left] <= target && target < nums[mid]) {
10 right = mid - 1;
11 } else {
12 left = mid + 1;
13 }
14 } else {
15 if (nums[mid] < target && target <= nums[right]) {
16 left = mid + 1
17 } else {
18 right = mid - 1;
19 }
20 }
21 }
22 return -1;
23};nums[left] <= nums[mid], tức là nửa trái đã sắp xếp.target nằm trong khoảng [nums[left], nums[mid]), thu hẹp phạm vi về bên trái.target nằm trong khoảng (nums[mid], nums[right]], tìm kiếm bên phải.