Daily bit(e) of C++ | Minimum in a rotated array
Daily bit(e) of C++ | Minimum in a rotated array
Daily bit(e) of C++ #259, Common interview problem: Minimum in a rotated array.
Today, we will look at a common C++ interview problem: Minimum in a rotated array.
Given an array of unique integers (std::vector<int>) that has been sorted in ascending order and then rotated by an unknown number of elements, return the minimum value in the array in O(logn).
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/7oYchz8Ed.
Solution
The O(logn) requirement points to a binary search. However, how to apply binary search to this problem might not be obvious.
Let’s observe that if we pick two elements, the minimum will be in between them if and only if value[left] > value[right]. This creates a half-open interval: the left element cannot be the minimum, but the right element still can be the minimum.
We can then apply this condition to binary search, following the partition that satisfies the value[left] > value[right] condition.
