812. Where the Rotation Begins
A list of n DISTINCT integers was sorted into increasing order and then rotated: some
prefix was lifted off the front and appended to the back. Rotating by 0 positions is allowed,
so the list may still be plainly sorted.
Print the number of positions it was rotated, which is the same as the 0-based index of the smallest element.
4 5 6 7 0 1 2 -> 4
1 2 3 4 5 -> 0
5 1 2 3 4 -> 1
2 3 4 5 1 -> 4
## What makes this different from the searches already in the bank
Problem 241 finds the first index whose value is at least x, and problems 261 and 262 are the
insertion-point and floor-and-ceiling readings of that same loop. Problem 107 finds a given
value. Problem 253 searches a rotated array for a value. Every one of them compares a[mid]
against a TARGET supplied in the input.
Here there is no target. The only thing a[mid] can be compared against is another element of
the array, and choosing which one is the whole problem.
## Choose a[hi], not a[0]
Compare a[mid] with a[hi], the last element of the CURRENT range.
Because the values are distinct, exactly one of two things is true.
a[mid] > a[hi] the descent from a high value to a low one happens somewhere
after mid, so the smallest element is at an index > mid
a[mid] < a[hi] the stretch mid .. hi contains no descent, so it is increasing,
so the smallest element is at an index <= mid
Comparing against a[0] instead looks equally plausible and is wrong. Once lo has moved past
the rotation point, a[0] is no longer related to the current range at all, and the test starts
answering a question about a part of the array you have already discarded. a[hi] is always
inside the live range, which is what makes it safe.
## The invariant the loop maintains
Start with lo = 0 and hi = n - 1, and keep this true at the top of every iteration:
> the index of the smallest element lies in [lo, hi].
The first branch discards lo .. mid, none of which can hold the minimum. The second discards
mid+1 .. hi, none of which can either, and keeps mid because mid may itself be the
answer. That is why it is hi = mid and not hi = mid - 1.
## Why the loop terminates
mid = lo + (hi - lo) / 2 gives lo <= mid < hi whenever lo < hi. One branch raises lo
above mid, the other lowers hi to mid, and both strictly shrink hi - lo. When
lo == hi the range holds exactly one index, and by the invariant that index is the answer.
## What is printed when the predicate never fires
If the list was not rotated at all, a[mid] < a[hi] on every single iteration, the loop only
ever takes the second branch, and lo never moves. It ends at 0, which is the correct rotation
count. Nothing special has to be written for that case, but it is worth checking, because an
implementation that starts hi at n rather than n - 1 reads past the end of the array on
the very first comparison.
## Size of the numbers
Nothing here overflows, and it is worth knowing why rather than assuming it. The values reach
10^9 in magnitude but are only ever compared, never added or multiplied, so a signed 32-bit
integer holds them with room to spare. The indices reach 200000, so lo + hi reaches
400000. Writing the midpoint as lo + (hi - lo) / 2 still costs nothing, and it is the
habit that saves you on problem 811, where the index range itself is 2 * 10^9.
## Cost
Time O(log n). Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - All values are distinct.
Input
The first line contains an integer n.
The second line contains n distinct integers, a sorted list that has been rotated left by some number of positions.
Output
Print one integer, the number of positions the list was rotated, equal to the 0-based index of the smallest element. Print it alone on one line, with nothing else.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.