Search in Rotated Array
A rotated sorted array is a sorted array that has been rotated at some pivot. Example: [4,5,6,7,0,1,2]. Searching for an element in such an array can be done in O(log n) time using a modified binary search.
Algorithm:
1. Find the pivot (the smallest element) using binary search.
2. Then binary search in the appropriate half.
Or combine both steps: compare target with the middle, determine which side is sorted, and decide.
Java implementation (single pass binary search):
public static int searchRotated(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[left] <= arr[mid]) {
// left half is sorted
if (target >= arr[left] && target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// right half is sorted
if (target > arr[mid] && target <= arr[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
Two Minute Drill
- Search in rotated sorted array using modified binary search.
- Time O(log n), space O(1).
- Determine which side is sorted and whether target lies in that side.
- Common interview problem.
Need more clarification?
Drop us an email at career@quipoinfotech.com