3.1 Rotated List
A rotated list or sorted circular array, is an array L =
[0; : : : ; n - 1] with a largest element L[m] > L[i], 0 i < n and L[i (mod n)] < L[i + 1 (mod n)], i 6= m.
We need dlg ne comparisons to find the positions of the
minimum and maximum elements in the array, or constant
time if we have maintained a dlg ne bits pointer to store m
explicitly for L.
This paper uses the same terminologies from Frederickson
(Frederickson 1983), where the rotated list L has