https://algodaily.com/challenges/fastminimuminrotatedarray
It seems we have to identify an element that is lower than the preceding one, as
this must be the original beginning of the array and thus the lowest. If we get
to the end of the array without finding a drop, then it must be the first
element of the array, as the pivot was at the end.
This still has a worst case running time of O(n) , though, as we might have to
iterate through the whole array.
Algo Daily‘s suggested solution is to use binary search, with a special
condition to check if it finds a sorted subsection, because we know the original
array was sorted.
If we hit a sorted subsection, we know that we’re next to the pivot, so we must
also be next to the original first element, which is the minimum.
function getMinimum(numbers) {
let left = 0;
let right = numbers.length  1;
while (left < right) {
// Is this section sorted? If so, the lefthand
// number must be the original first element and
// thus the minimum.
if (numbers[left] < numbers[right]) {
return numbers[left];
}
let midpoint = Math.floor((left + right) / 2);
if (numbers[midpoint] >= numbers[left]) {
// The midpoint is higher; keep searching in
// the righthand side.
left = midpoint + 1;
} else {
// The midpoint is lower; keep searching in
// the lefthand side.
right = midpoint;
}
// Eventually left will = right.
}
return numbers[left];
}
View post:
AlgoDaily 19: Fast Minimum In Rotated Array
