Search in Rotated Sorted Array

Longest Consecutive Sequence

Rotate Image

Find a target value's index in an ascending array that has been rotated at an unknown pivot.

You are given an integer array `nums` sorted in ascending order (with distinct values), then rotated at some unknown pivot index. Given `nums` and an integer `target`, return the index of `target` in `nums`, or `-1` if it is not present. You must write an algorithm with `O(log n)` runtime complexity.

**Input / output**
- Input: `nums: integer[]` (rotated ascending, distinct values), `target: integer`
- Output: `integer`, the index of `target`, or `-1`

**Examples**
1. `nums = [4,5,6,7,0,1,2], target = 0` returns `4`.
2. `nums = [4,5,6,7,0,1,2], target = 3` returns `-1` because `3` is not in the array.
3. `nums = [1], target = 0` returns `-1`.

**Constraints**
- `1 <= nums.length <= 5,000`
- `-10,000 <= nums[i] <= 10,000`
- All values of `nums` are unique.
- `nums` is an ascending array possibly rotated at an unknown pivot.

**Follow-up**
How would your approach change if duplicate values were allowed, and why can that force worst-case `O(n)`?

- The array was sorted ascending, then rotated at some unknown pivot (e.g. `[0,1,2,4,5,6,7]` rotated at index 3 becomes `[4,5,6,7,0,1,2]`).
- You need to find `target`'s index in `O(log n)` — a plain linear scan is `O(n)` and defeats the point of the problem.
- Key insight: even though the whole array isn't sorted, at least one of the two halves around any midpoint always *is* sorted. That's enough to still binary search.

Understanding the Problem

- Keep `lo`/`hi` pointers like standard binary search. At each step compute `mid`.
- Determine which half is sorted by comparing `nums[lo]` and `nums[mid]`: if `nums[lo] <= nums[mid]`, the left half `[lo..mid]` is sorted; otherwise the right half `[mid..hi]` is sorted.
- Once you know which half is sorted, checking whether `target` lies within that half's value range is a simple comparison. If it does, search that half; otherwise, search the other half.

Modified Binary Search

- If `nums[mid] == target`, return `mid` immediately.
- If left half `[lo..mid]` is sorted: `target` is in it exactly when `nums[lo] <= target < nums[mid]`, so narrow `hi = mid - 1`; otherwise narrow `lo = mid + 1`.
- If the right half `[mid..hi]` is sorted instead: `target` is in it exactly when `nums[mid] < target <= nums[hi]`, so narrow `lo = mid + 1`; otherwise narrow `hi = mid - 1`.
- Loop while `lo <= hi`; if the loop ends without finding `target`, return `-1`.

Working Through the Branches

This still runs in `O(log n)` time and `O(1)` space — the halving still happens every iteration, just with an extra comparison to figure out which half is sorted.

Final Solution (all languages)

- Using `nums[lo] < nums[mid]` instead of `<=` to detect the sorted half — with only 1-2 elements in a half, `lo == mid` and the strict inequality misclassifies it as unsorted.
- Off-by-one errors in the range checks (`<` vs `<=` at the boundaries) — easy to skip or double-count the boundary element.
- Follow-ups: how does the approach change if the array can contain duplicates (values equal to `nums[lo]` making it ambiguous which half is sorted — worst case degrades to `O(n)`)? How would you find the rotation pivot index itself?