Why?
I was solving a leetcode problem which states
Given a sorted array
nums
that is rotated at an unknown pivot, return the index of the target value if it exists in the array; otherwise, return-1
. The solution must have a runtime complexity ofO(log n)
.
I realized that the given array is a sorted array that has been rotated at an unknown pivot. This insight led me to consider using a modified binary search to achieve the required O(log n)
runtime complexity. The main challenge is to determine which part of the array (left or right of the middle element) is sorted and then decide where to search for the target.
Approach
The solution uses a binary search approach with a slight modification to handle the rotated array:
-
Initialize Pointers: Start with two pointers,
lo
andhi
, representing the start and end of the array, respectively. -
Binary Search Loop: While
lo
is less than or equal tohi
:- Calculate the middle index,
mid
. - Check if the middle element is the target. If yes, return its index.
- Determine which part of the array is sorted:
- If the left part (
nums[lo]
tonums[mid]
) is sorted: - Check if the target lies within this range. If so, adjust
hi
tomid - 1
. - Otherwise, adjust
lo
tomid + 1
to search in the unsorted right part. - If the right part (
nums[mid]
tonums[hi]
) is sorted: - Check if the target lies within this range. If so, adjust
lo
tomid + 1
. - Otherwise, adjust
hi
tomid - 1
to search in the unsorted left part.
- If the left part (
- Calculate the middle index,
-
Return the Result: If the target is not found, return
-1
.
Complexity
-
Time Complexity: The time complexity is
O(log n)
because the binary search reduces the search space by half in each iteration. -
Space Complexity: The space complexity is
O(1)
since we are using only a few extra variables.
Code
class Solution {
public int search(int[] nums, int target) {
int lo = 0;
int hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
// Check if the left part is sorted
if (nums[lo] <= nums[mid]) {
if (nums[lo] <= target && target < nums[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
// Otherwise, the right part must be sorted
else {
if (nums[mid] < target && target <= nums[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return -1;
}
}
By using this approach, we efficiently find the target in a rotated sorted array with logarithmic time complexity, making it suitable for large datasets.
Top comments (0)