Search in Rotated Sorted Array

Problem Statement

Given a sorted array that has been rotated at some unknown pivot, search for a target value. Return its index, or -1 if not found.

You must solve it in O(log n) time.

Constraints

• 1 <= nums.length <= 10^4
• All values are unique
• Array was originally sorted ascending, then rotated
• -10^4 <= nums[i], target <= 10^4

Example

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

What the Interviewer Expects

1. Key insight — even after rotation, at least one half of the array (relative to mid) is always sorted.
2. Modified binary search:
   • Find mid
   • Determine which half is sorted (compare nums[left] with nums[mid])
   • Check if target lies within the sorted half's range → search there
   • Otherwise search the other half
3. O(log n) — this is the required complexity. A linear scan is a fail.
4. Edge cases — single element, target at pivot, no rotation (fully sorted).

Follow-ups

1. What if the array contains duplicates? How does that affect the complexity? (Worst case O(n))
2. How do you find the rotation pivot index itself in O(log n)?
3. What if you need to find the minimum element in the rotated array?
4. Can you find how many times the array was rotated?