Search in Rotated Sorted Array

There is an integer array nums that was sorted in ascending order with distinct values but then rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Given target, return its index in nums, or -1 if it is not in nums. You must write an O(log n) algorithm.

• In a rotated sorted array, one of the two halves [left..mid] or [mid..right] is always sorted. We can check which half contains target and narrow the search.

• At each step, nums[mid] splits the range. Either the left half [left..mid] is sorted (nums[left] <= nums[mid]) or the right half [mid..right] is sorted. If the left half is sorted and target is in [nums[left], nums[mid]], search left; otherwise search right. If the right half is sorted and target is in [nums[mid], nums[right]], search right; otherwise search left.
• We always eliminate one half, so the search is O(log n).

High-level: Binary search. If nums[left] <= nums[mid], the left half is sorted: if nums[left] <= target < nums[mid], search left (right = mid - 1); else search right (left = mid + 1). If nums[mid] < nums[right], the right half is sorted: if nums[mid] < target <= nums[right], search right; else search left. Return -1 if not found.

Steps:

1. left = 0, right = n - 1. While left <= right: mid = left + (right - left) / 2. If nums[mid] == target return mid.
2. If nums[left] <= nums[mid]: if nums[left] <= target && target < nums[mid], right = mid - 1; else left = mid + 1. Else: if nums[mid] < target && target <= nums[right], left = mid + 1; else right = mid - 1.
3. Return -1.

• Time: O(log n).
• Space: O(1).

• Duplicate values: worst case O(n).