Search in Rotated Sorted Array in Java

You are given an array of distinct integers nums that was sorted in ascending order and then possibly rotated at an unknown index k (0 <= k < nums.length): its first k elements were moved, in the same order, to its end. For example, [0,1,2,4,5,6,7] rotated at k = 3 becomes [4,5,6,7,0,1,2], and with k = 0 it stays as it was.

Given nums after the rotation and an integer target, return the index of target in nums, or -1 if target is not in nums.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Explanation: 0 is at index 4.

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Explanation: 3 is not in nums.

Example 3:

Input: nums = [6,7,1,2,3,4,5], target = 7
Output: 1
Explanation: The middle element is nums[3] = 2. The half from index 3 to the end, [2,3,4,5], is sorted, and 7 is not between 2 and 5, so 7 can only be in the other half, [6,7,1]. Searching that half finds 7 at index 1.

Constraints:

• 1 <= nums.length <= 106
• -109 <= nums[i] <= 109
• All the values of nums are distinct.
• nums is sorted in ascending order and possibly rotated.
• -109 <= target <= 109