Intermediate Level
Implement the searchRotatedSortedArrayImportant method that searches for a target in a rotated sorted array using binary search.
The input contains a rotated sorted integer array nums, its length size, and a target value. The array was originally sorted in ascending order, then rotated from some position.
Your task is to return the index of target. If the target does not exist in the array, return -1.
For example, [4,5,6,7,0,1,2] is a rotated sorted array. The value 0 is found at index 4.
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 current range must still be sorted. Compare nums[left], nums[mid], and nums[right] to decide whether the left half or the right half is sorted.
If the target lies inside the sorted half, continue searching there. Otherwise, search in the other half.
Pseudocode:
function searchRotatedSortedArrayImportant(nums, size, target):
left = 0
right = size - 1
while left <= right:
mid = left + (right - left) / 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