Array Binary Search
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) = 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 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 -1
Run your code to see the result.