What is a Rotated Sorted Array?
Consider a sorted array, for example:
[1, 2, 3, 4, 5, 6]
Now, if this array is rotated at some pivot, say at index 3, it would become:
[4, 5, 6, 1, 2, 3]
Notice that the array is still sorted, but it is divided into two parts. Our goal is to search for a target value in such arrays efficiently.
The Search Strategy
To search in a rotated sorted array, we need to:
- Find the Pivot: The pivot is the point where the array transitions from larger to smaller values.
- Binary Search: Once we find the pivot, we can use binary search on the appropriate half of the array.
Step-by-Step Code Explanation
class Solution {
public static void main(String[] args) {
int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
int target = 5;
// Searching for the target
int result = search(arr, target);
// Displaying the result
System.out.println("Index of target: " + result);
}
// Main search function to find the target in a rotated sorted array
public static int search(int[] nums, int target) {
// Step 1: Find the pivot
int pivot = searchPivot(nums);
// Step 2: If no pivot, perform regular binary search
if (pivot == -1) {
return binarySearch(nums, target, 0, nums.length - 1);
}
// Step 3: If the target is at the pivot, return the pivot index
if (nums[pivot] == target) {
return pivot;
}
// Step 4: Decide which half of the array to search
if (target >= nums[0]) {
return binarySearch(nums, target, 0, pivot - 1); // Search left side
} else {
return binarySearch(nums, target, pivot + 1, nums.length - 1); // Search right side
}
}
// Binary search helper function
static int binarySearch(int[] arr, int target, int start, int end) {
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[mid] == target) {
return mid; // Target found
} else if (target < arr[mid]) {
end = mid - 1; // Search left half
} else {
start = mid + 1; // Search right half
}
}
return -1; // Target not found
}
// Function to find the pivot index in a rotated sorted array
static int searchPivot(int[] arr) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
// Check if mid is the pivot point
if (mid < end && arr[mid] > arr[mid + 1]) {
return mid;
}
// Check if the pivot is before the mid
if (mid > start && arr[mid] < arr[mid - 1]) {
return mid - 1;
}
// Decide whether to move left or right
if (arr[mid] <= arr[start]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1; // No pivot found (array is not rotated)
}
}
Explanation of the Code
-
search():- This function is responsible for searching for the target in the rotated sorted array.
- First, we find the pivot using the
searchPivot()function. - Depending on the pivot's position, we then decide which half of the array to search using binary search.
-
binarySearch():- A standard binary search algorithm to find the target in a sorted sub-array.
- We define the
startandendindices and progressively narrow the search space.
-
searchPivot():- This function identifies the pivot point (the place where the array rotates).
- The pivot is the index where the sorted order is "broken" (i.e., the array goes from a higher value to a lower value).
- If no pivot is found, it means the array was not rotated, and we can perform a regular binary search.
How the Algorithm Works
For an array like [4, 5, 6, 1, 2, 3]:
- The pivot is at index 2 (
6is the largest, and it is followed by1, the smallest). - We use this pivot to divide the array into two parts:
[4, 5, 6]and[1, 2, 3]. - If the target is greater than or equal to the first element (
4in this case), we search the left half. Otherwise, we search the right half.
This method ensures that we search efficiently, achieving a time complexity of O(log n), similar to a standard binary search.
Conclusion
Rotated sorted arrays are a common interview question and a useful challenge to deepen your understanding of binary search. By finding the pivot and adapting our binary search accordingly, we can efficiently search through the array in logarithmic time.
If you found this article helpful, feel free to connect with me on LinkedIn or share your thoughts in the comments! Happy coding!
Top comments (0)