The “Search in Rotated Sorted Array” problem involves finding a target value in a sorted array that’s been rotated at some unknown pivot. For instance, an array like [4,5,6,7,0,1,2] is a rotation of [0,1,2,4,5,6,7]. You’re given this rotated array and a target value; your goal is to determine the target’s index if it exists or return -1 if it doesn’t.
1. A rotated sorted array is a sorted array that has been rotated at a pivot. For example:
• Original: [1, 2, 3, 4, 5, 6, 7]
• Rotated: [4, 5, 6, 7, 1, 2, 3]
2. The challenge is to find the target value in O(\log n) time. This means using binary search, but modified to account for the rotation.
Brute Force Approach
A simple way to solve this problem is by linearly searching through each element in the array, checking if it matches the target.
public int search(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i; // Return index if target found
}
}
return -1; // Return -1 if target not found
}
The code iterates over each element in the array (nums) and checks if the current element (nums[i]) equals the target. If it finds the target, it returns the index; if it completes the loop without finding it, it returns -1. While this method is simple, it takes O(n) time, which can be inefficient for large arrays.
Optimal Solution: Using Binary Search
Since the array is sorted but rotated, we can take advantage of binary search to solve this in O(log n) time. The rotation causes the array to have two sorted subarrays, so binary search can be modified to work in each half by checking if the middle element lies in the same sorted portion as the target.
Binary search is effective here because:
1. The array is sorted in segments, with one segment guaranteed to be sorted.
2. The problem requires an efficient search (less than O(n)), which binary search provides with O(log n) complexity.
These characteristics align with the typical binary search pattern, which is ideal when a sorted structure can be divided to search more quickly.
Step-By-Step Algorithm
To efficiently locate the target:
1. Split the Array Using Binary Search:
• Use the mid-point to divide the array into two halves.
• One of the halves will always be sorted due to the nature of the rotation.
2. Decide Which Half to Search:
• If the target is within the sorted half, narrow the search range to this half.
• Otherwise, search the other half.
3. Repeat Until the Target is Found:
• Continue adjusting the search range until you either find the target or exhaust the array.
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Check if mid element is the target
if (nums[mid] == target) {
return mid;
}
// Determine which half is sorted
if (nums[left] <= nums[mid]) { // Left half is sorted
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // Target is in left half
} else {
left = mid + 1; // Target is in right half
}
} else { // Right half is sorted
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // Target is in right half
} else {
right = mid - 1; // Target is in left half
}
}
}
return -1; // Target not found
}- Initialize Left and Right Pointers
int left = 0;
int right = nums.length - 1;- Sets up two pointers, left at the beginning of the array and right at the end.
- These pointers are the boundaries of the part of the array we’re currently searching. They will move inward as we narrow down the search range, similar to binary search.
2. Binary Search Loop
while (left <= right) {
• Binary search divides the array into halves repeatedly, so this loop keeps it going until the target is found or the range is exhausted.
3. Calculate The Middle
int mid = left + (right - left) / 2;- Binary Search works by splitting the range into two halves and eliminating one half each step.
4. Check if the middle element is the target
if (nums[mid] == target) {
return mid;
}- This ensures we don’t search unnecessarily if the target is already found.
5. Determine Which Half Is Sorted
if (nums[left] <= nums[mid]) { // Left half is sorted- Check if the left half of the array (from nums[left] to nums[mid]) is sorted
- In a rotated sorted array, one half of the current range is always sorted. Knowing which half is sorted helps decide where to search.
6. Check if Target is in the Sorted Left Half
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // Target is in left half
} else {
left = mid + 1; // Target is in right half
}- If the target lies within the sorted left half (nums[left] <= target < nums[mid]), move the right pointer to focus on the left half.
- Narrows down the search range to the part of the array that might contain the target.
7. If The Right Half Is Sorted
} else {- if the left half is not sorted, the right half must be sorted (because one half is always sorted in a rotated array).
8. Is The Target In The Right Half
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // Target is in right half
} else {
right = mid - 1; // Target is in left half
}• If the target is between nums[mid] and nums[right] (inclusive of nums[right] and exclusive of nums[mid]), the target must be in the right half.
• Move left to mid + 1 to search the right half.
• Otherwise, the target is in the left half.
• Move right to mid – 1 to search the left half.
Key Insights
1. Rotation Property:
• One half of the array is always sorted. This property helps decide where to search.
2. Efficient Search:
• By leveraging the sorted half, the algorithm eliminates unnecessary comparisons and maintains O(\log n) time complexity.
3. Binary Search with a Twist:
• This is a variation of binary search that adapts to the rotation, making it an elegant and efficient solution for the problem.
