Rotated Array Pattern
What is a Rotated Sorted Array?
A rotated sorted array is a sorted array that has been rotated at some pivot point. For example, [4, 5, 6, 7, 0, 1, 2] is a rotated version of [0, 1, 2, 4, 5, 6, 7].
Binary search can be adapted to efficiently search in rotated sorted arrays.
Key Insights
- Partial Sorting: Even though the array is rotated, each half of the array (divided by the pivot) is still sorted
- Identifying Sorted Half: By comparing elements, we can determine which half of the array is sorted
- Leveraging Sorted Half: Once we know which half is sorted, we can check if the target is in that half
- Eliminating Half: Based on our check, we can eliminate half of the array in each step, just like in standard binary search
Searching in a Rotated Sorted Array
Here's how to search for a target value in a rotated sorted array:
Finding the Minimum in a Rotated Sorted Array
Another common problem is finding the minimum element in a rotated sorted array:
Common Challenges
- Handling Duplicates: When the array contains duplicates, it becomes harder to determine which half is sorted
- Edge Cases: Be careful with edge cases like an array with only one element or an array that is not rotated
- Pivot Identification: Sometimes you need to find the pivot (rotation point) first, then perform a standard binary search
Pattern 2: Rotated Array
Learn how to adapt binary search to work with sorted arrays that have been rotated.
What is a Rotated Sorted Array?
A rotated sorted array is a sorted array that has been rotated at some pivot point. For example, [4, 5, 6, 7, 0, 1, 2] is a rotated version of [0, 1, 2, 4, 5, 6, 7].
Despite the rotation, binary search can still be applied with some modifications.
Example:
Original Sorted Array: [0, 1, 2, 4, 5, 6, 7]
After Rotation: [4, 5, 6, 7, 0, 1, 2]
Explanation: The array was rotated at index 4, moving the first 4 elements to the end.
Key Insights
Partial Sorting
Even though the array is rotated, each half of the array (divided by the pivot) is still sorted.
Identifying Sorted Half
By comparing elements, we can determine which half of the array is sorted.
Leveraging Sorted Half
Once we know which half is sorted, we can check if the target is in that half.
Eliminating Half
Based on our check, we can eliminate half of the array in each step, just like in standard binary search.
Searching in a Rotated Sorted Array
Here's how to search for a target value in a rotated sorted array:
1234567891011121314151617181920212223242526272829303132333435function search(nums, target) { let left = 0; let right = nums.length - 1; while (left <= right) { const mid = Math.floor((left + right) / 2); // Found the target if (nums[mid] === target) { return mid; } // Check if the left half is sorted if (nums[left] <= nums[mid]) { // Check if target is in the left half if (nums[left] <= target && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } // Right half is sorted else { // Check if target is in the right half if (nums[mid] < target && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } // Target not found return -1;}How it works: In each step, we determine which half of the array is sorted by comparing nums[left] with nums[mid]. Then, we check if the target is within the range of the sorted half. If it is, we search that half; otherwise, we search the other half.
Finding the Minimum in a Rotated Sorted Array
Another common problem is finding the minimum element in a rotated sorted array:
123456789101112131415161718192021222324252627function findMin(nums) { let left = 0; let right = nums.length - 1; // If the array is not rotated if (nums[left] < nums[right]) { return nums[left]; } while (left < right) { const mid = Math.floor((left + right) / 2); // If mid element is greater than the rightmost element, // the minimum is in the right half if (nums[mid] > nums[right]) { left = mid + 1; } // If mid element is less than or equal to the rightmost element, // the minimum is in the left half (including mid) else { right = mid; } } // At this point, left == right and points to the minimum element return nums[left];}How it works: We compare the middle element with the rightmost element. If the middle element is greater than the rightmost element, the minimum must be in the right half. Otherwise, the minimum must be in the left half (including the middle element itself).
Common Challenges and Edge Cases
Handling Duplicates
When the array contains duplicates, it becomes harder to determine which half is sorted.
Solution: In the worst case, you might need to linearly scan the array, but you can often skip duplicates at the boundaries.
Edge Cases
Be careful with edge cases like an array with only one element or an array that is not rotated.
Solution: Add special checks for these cases at the beginning of your function.
Pivot Identification
Sometimes you need to find the pivot (rotation point) first, then perform a standard binary search.
Solution: You can find the pivot using a modified binary search, then perform two standard binary searches on each sorted half.
Multiple Rotations
An array might be rotated multiple times, but it's equivalent to a single rotation.
Solution: The algorithms work regardless of how many times the array has been rotated.