Q8: How do you search for a target value in a Rotated Sorted Array in O(log n) time?
Use Modified Binary Search. In a rotated sorted array, at least one half (left to mid OR mid to right) is guaranteed to be strictly sorted. Determine which half is sorted, check if target lies within its bounds, and adjust binary search boundaries left / right accordingly.
Rotated Sorted Array Search
public class RotatedSearch {
public static int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) { // Left half sorted
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else { // Right half sorted
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
}💡 Determines the sorted sub-array half to locate target boundaries in logarithmic time.
Key Takeaways
- Identify the sorted half in each binary search step.
- Narrows search range in $O(log n)$ time.
Knowledge Check
How do you calculate mid safely in Java binary search to prevent integer overflow?