Intermediate Level
Implement the searchInRotatedSortedArray method that searches for a target inside a rotated sorted array.
The input contains a rotated sorted array nums, its length size, and an integer target. Your task is to return the index of target in the array.
A rotated sorted array was originally sorted in ascending order, then shifted from some position. For example, [4,5,6,7,0,1,2] is a rotated version of a sorted array. If the target is not present, return -1.
Example 1
Input
nums (int[]) =
[4,5,6,7,0,1,2]size (int) =
7target (int) =
0Returns (int)
4Example 2
Input
nums (int[]) =
[4,5,6,7,0,1,2]size (int) =
7target (int) =
3Returns (int)
-1Example 3
Input
nums (int[]) =
[1]size (int) =
1target (int) =
1Returns (int)
0Use a modified binary search.
At every step, one half of the array is still sorted. Check whether the left half or right half is sorted, then decide whether the target lies inside that sorted half. Search only in the half where the target can exist.
This avoids scanning the complete array.
Pseudocode:
function searchInRotatedSortedArray(nums, size, target):
left = 0
right = size - 1
while left <= right:
mid = (left + right) / 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target and target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run