AlgoDaily 19: Fast Minimum In Rotated Array

https://algodaily.com/challenges/fast-minimum-in-rotated-array

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 left-hand
		// 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 right-hand side.
			left = midpoint + 1;
		} else {
			// The midpoint is lower; keep searching in
			// the left-hand side.
			right = midpoint;
		}

		// Eventually left will = right.
	}

	return numbers[left];
}