Searching in a rotated sorted array is a common problem in coding interviews and can be efficiently solved using a modified binary search algorithm. A rotated sorted array is one that has been sorted and then rotated at some pivot point. For example, the array [4, 5, 6, 7, 0, 1, 2]
is a rotated version of the sorted array [0, 1, 2, 4, 5, 6, 7]
.
Problem Statement
Given a rotated sorted array and a target value, you need to determine if the target exists in the array and return its index if it does. If the target does not exist, return -1.
Approach
- Identify the Pivot: The pivot is the point where the rotation has occurred. This can be found using a modified binary search.
- Determine Which Side to Search: Once you have the pivot, you can determine which side of the array to search based on the target’s value.
- Perform Binary Search: Depending on which half the target may exist in, perform a standard binary search on that half.
C# Implementation
Here’s how you can implement this approach in C#:
public class Solution
{
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 is the target
if (nums[mid] == target)
return mid;
// Determine which side is sorted
if (nums[left] <= nums[mid]) // Left side is sorted
{
if (nums[left] <= target && target < nums[mid]) // Target in left side
right = mid - 1;
else // Target in right side
left = mid + 1;
}
else // Right side is sorted
{
if (nums[mid] < target && target <= nums[right]) // Target in right side
left = mid + 1;
else // Target in left side
right = mid - 1;
}
}
return -1; // Target not found
}
}
Explanation of the Code
- Initialization: We initialize two pointers,
left
andright
, to represent the bounds of our search space. - Binary Search Loop: The while loop continues until the search space is empty (
left
exceedsright
). - Mid Calculation: We calculate the midpoint to check if it equals the target.
- Identifying Sorted Halves:
- If the left half is sorted (
nums[left] <= nums[mid]
), we check if the target is within this range. If it is, we adjust our search space to the left half; otherwise, we search the right half. - If the right half is sorted, we do the opposite check.
- If the left half is sorted (
- Return Statement: If we exit the loop without finding the target, we return -1.
Complexity
- Time Complexity: O(log n) due to the binary search.
- Space Complexity: O(1) since we’re using a constant amount of space.
This method effectively handles the search in a rotated sorted array, leveraging the properties of both binary search and the sorted nature of the array.