Binary Search in Rotated Sorted Array

Problem Context

You are given a sorted array of distinct integers that has been rotated at an unknown pivot index. For example, [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2] after a rotation.

Your task is to implement an efficient search algorithm to find a given target value in this rotated array. If the target exists, return its index. Otherwise, return -1.

Key Challenge: You must achieve O(log n) time complexity — a naive linear scan is not acceptable.

Input / Output Format

Input:

• nums — a list of distinct integers, originally sorted in ascending order, then rotated at some pivot
• target — an integer to search for

Output:

• Return the index of target in nums, or -1 if it is not present

Examples

Example 1

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

Example 2

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.

Example 3

Input:  nums = [1], target = 0
Output: -1
Explanation: The single-element array does not contain the target.

Approach Hints

1. Standard Binary Search compares the middle element with the target and eliminates half the search space. But a rotated array isn't fully sorted — how do you handle this?

2. Key Insight: Even though the array is rotated, at least one half of the array (left or right of mid) is always sorted. You can use this property:

   • If nums[left] <= nums[mid], the left half is sorted.
   • Otherwise, the right half is sorted.

3. Once you identify the sorted half, check if the target lies within that sorted range. If yes, search that half; otherwise, search the other half.

4. Think about time complexity: Each iteration eliminates half the elements → O(log n). Space complexity is O(1) for an iterative solution.

Follow-up Questions (Expect These in an Interview)

• Can you solve it recursively? What's the space complexity then?
• What changes if the array contains duplicates? (Hint: the time complexity guarantee breaks.)