Array Sorting Binary Search Two Pointers
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) = 7
target (int) = 0
Return:
(int) 4
Example 2
Input:
nums (int[]) = [4,5,6,7,0,1,2]
size (int) = 7
target (int) = 3
Return:
(int) -1
Example 3
Input:
nums (int[]) = [1]
size (int) = 1
target (int) = 1
Return:
(int) 0

Use 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 -1
Run your code to see the result.