74. Search in a Rotated Sorted Array

An ascending array was rotated at some unknown pivot. Given the rotated array and a target, find the target's index, or print -1 if it isn't present.

Input: The first line contains an integer n. The second line contains n space-separated distinct integers. The third line contains the target value. Output: Print a single integer - the index of the target, or -1 if it isn't present.

1 <= n <= 10^5, all elements distinct

This builds directly on 'Find the Pivot Element' - one valid alternative solution is finding the pivot first, then doing two clean binary searches on the resulting genuinely-sorted sub-arrays, though the single-pass combined approach shown here avoids the extra pivot-finding step.

Search for a target value in an array that was originally sorted but has since been rotated at some unknown point. Brute force: Scan the array linearly checking each element against the target - this costs O(n), completely correct but discards the huge advantage of the array's underlying sorted (just rotated) structure. Optimised: At every step, exactly ONE of the two halves is guaranteed to be genuinely sorted (never both rotated) - checking which one it is, and whether the target's value falls within that half's known range, lets you eliminate half the search space every step, exactly like standard binary search.

Scan through the array from start to end comparing each element to the target and return its index the moment a match is found, or -1 if the scan finishes without one. This ignores the fact that the array is a rotated sorted array entirely and treats it like an arbitrary unsorted list. Time: O(n) Space: O(1)

First binary search for the rotation pivot (the index of the minimum element, found by comparing mid to the last element to decide which half is unrotated), which splits the array into two sorted subarrays. Then determine which of those two subarrays could contain the target based on its value relative to the endpoints, and run a standard binary search restricted to that subarray. This exploits the sortedness within each half using two clean binary searches instead of one linear scan. Time: O(log n) Space: O(1)

Run one binary search where, at each step, first determine whether the left half [left, mid] or right half [mid, right] is the sorted one by comparing arr[left] to arr[mid], then check if the target falls within that sorted half's range to decide which side to recurse into, otherwise go the other way. This finds the target with a single binary search pass instead of a separate pivot-finding search followed by a second search, halving the number of comparisons needed in practice while keeping the same asymptotic bound. Time: O(log n) Space: O(1)

1. At each binary search step, compare arr[lo], arr[mid], and arr[hi] to determine which HALF of the current range is genuinely sorted (one half always is, even in a rotated array). 2. Check if the target falls within that sorted half's value range. 3. If it does, search that half; otherwise, search the other half - repeat until found or the range is exhausted.

Time: O(log n) - a modified binary search. Space: O(1) - just a few pointer variables.

Test n = 1, a target absent from the array (-1), an array that wasn't rotated at all, and n = 10^5 for performance.

Be ready to carefully trace through the FOUR possible cases (target in the sorted left half, target not in the sorted left half, and the mirror two cases when the right half is the sorted one) - getting the comparisons exactly right here is the main challenge of this well-known problem.