813. The Smallest Value When Copies Are Allowed
A list of n integers was sorted into NON-DECREASING order, so equal values are allowed, and
then rotated left by some number of positions.
Print the smallest value in the list.
2 2 2 0 1 1 2 -> 0
3 3 3 3 3 -> 3
10 1 10 10 10 10 -> 1
1 2 2 2 2 2 -> 1
## Why this asks for a value and problem 812 asks for an index
Problem 812 prints the POSITION of the smallest element, which is also the rotation count, because with distinct values the rotation count is uniquely determined.
Duplicates destroy that. The list 2 2 2 is what you get by rotating 2 2 2 by zero, one or
two positions, and no algorithm can tell which happened. Asking for an index would be asking
for information the input does not contain. So the question changes to one that is still well
posed, the smallest VALUE, and that difference is the point of the pair.
## Where the comparison stops working
Problem 812 compares a[mid] with a[hi] and exactly one of > and < holds. With
duplicates a third case appears.
a[mid] > a[hi] the descent is after mid -> lo = mid + 1
a[mid] < a[hi] mid .. hi is free of the descent -> hi = mid
a[mid] == a[hi] no information at all
The third case really is no information. Look at 1 0 1 1 1 1 1 and 1 1 1 1 1 0 1. Both
have a[mid] == a[hi] == 1 with the same length, and the smallest element is on opposite sides.
No comparison of those two entries can distinguish them, so no rule based on them can be
correct.
## What to do with the tie, and why it is safe
When a[mid] == a[hi], do hi = hi - 1.
This is safe because a[hi] is not needed: it has a twin at mid, still inside the range, and
that twin holds a value no larger. Formally, if a[hi] was a minimum of the range then
a[mid] is one too, and mid <= hi - 1, so the minimum VALUE of [lo, hi-1] equals the
minimum value of [lo, hi]. Dropping one end never changes the answer.
## The invariant the loop maintains
> the smallest value of the whole list is equal to the smallest value of a[lo .. hi].
All three branches preserve it: the first two discard a side that provably contains no value smaller than what remains, the third discards a duplicate.
## Why the loop terminates
Every branch lowers hi or raises lo by at least one, so hi - lo strictly decreases and
the loop ends with lo == hi. By the invariant, a[lo] is then the smallest value.
The cost, however, is no longer logarithmic. On a list of ones with a single zero buried in it,
the tie branch fires almost every time and the loop makes O(n) iterations. That is
unavoidable, by the indistinguishability argument above, and it is why this problem is harder
than problem 812 rather than merely longer.
## What is printed when the predicate never fires
If every value is identical, only the tie branch ever runs, hi walks all the way down to
lo = 0, and the answer is a[0], the value everything shares. That case is in the tests.
## Size of the numbers
As in problem 812, nothing overflows: the values reach 10^9 but are only compared, and the
indices reach 200000, so even lo + hi stays tiny for a 32-bit integer. The reason to
keep writing lo + (hi - lo) / 2 anyway is that the same loop turns up in problems where the
range IS the number, and a habit that only works sometimes is worse than no habit.
## Cost
Time O(log n) when the values are distinct, O(n) in the worst case. Space O(1) beyond
the input.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000` - Values may repeat.
Input
The first line contains an integer n.
The second line contains n integers, a non-decreasing list that has been rotated left by some number of positions. Values may repeat.
Output
Print one integer, the smallest value present in the list. Print it alone on one line, with no index and no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.