Java - Search in Rotated Sorted Array
Problem Statement
Given a rotated sorted array and a target value, return the index of the target if found. Otherwise, return -1.
Example
Input:
nums = [4, 5, 6, 7, 0, 1, 2];
target = 0;
Output:
4
Explanation:
The array [4, 5, 6, 7, 0, 1, 2] is a rotated version of [0, 1, 2, 4, 5, 6, 7].
0 is found at index 4.
Approach
Binary Search (O(log N))
Find the sorted half:
If nums[mid] >= nums[left], then the left half is sorted.
Otherwise, the right half is sorted.
Decide the search direction:
If the target lies in the sorted half, search there.
Otherwise, search in the unsorted half.
Java Code
public class RotatedSortedArraySearch {
public static int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Target found
if (nums[mid] == target) {
return mid;
}
// Left half is sorted
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
// Right half is sorted
else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
System.out.println("Index of " + target + ": " + search(nums, target));
}
}
