Search in Rotated Sorted Array

An array sorted in ascending order is rotated at an unknown pivot. Given the array and a target, return the index of the target or -1 if not found. All values are distinct.

Function signature

func Search(nums []int, target int) int

Inputs / outputs

• nums: rotated sorted array with distinct values.
• target: value to search.
• Return: index of target, or -1.

Example

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

Constraints

• 1 <= len(nums) <= 100_000

Core idea (near-solution)

Binary search by identifying which half is sorted. The target must lie in one of the halves.

Invariant: the target (if it exists) is always within the current [lo, hi] range.

Algorithm (step-by-step)

1. Set lo = 0, hi = len(nums)-1.
2. While lo <= hi:
   • mid = lo + (hi-lo)/2.
   • If nums[mid] == target, return mid.
   • If left half is sorted (nums[lo] <= nums[mid]):
     • If nums[lo] <= target < nums[mid], move left (hi = mid-1), else move right.
   • Else right half is sorted:
     • If nums[mid] < target <= nums[hi], move right (lo = mid+1), else move left.
3. Return -1.

Correctness sketch

• Invariant: the target (if it exists) is always within the current [lo, hi] range.
• The valid answer lies within the maintained [lo, hi] range.
• Each comparison discards half the range that cannot contain an answer.
• When the loop ends, the remaining boundary/index is correct.

Trace (hand walkthrough)

Example input:
nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Walk:
- lo=0 hi=6 mid=3 val=7; left sorted [4..7], target 0 not in -> lo=4
- lo=4 hi=6 mid=5 val=1; left sorted [0..1], target 0 in -> hi=4
- mid=4 val=0 -> found index 4

Pitfalls to avoid

• Misplacing the boundary comparisons (<= vs <).
• Forgetting the distinct-values assumption; this logic relies on it.

Complexity

• Time: O(log n).
• Extra space: O(1).

Implementation notes (Go)

• Use lo + (hi-lo)/2 to avoid overflow.