Find Minimum in Rotated Sorted Array
A sorted array was rotated at an unknown pivot. For example, [10, 20, 30, 40, 50]
becomes [30, 40, 50, 10, 20]
. Find the index of the minimum element in this array.
Input: [30, 40, 50, 10, 20]
Output: 3
Explanation: the smallest element is 10 and its index is 3.
Try it yourself
Explanation
At first glance, it seems that there's no way to do it in less than linear time. The array is not sorted.
But remember binary search can work beyond sorted array, as long as there is a binary decision we can use to shrink the search range.
Let's draw a figure and see if there's any pattern. If we plot the numbers against their index, we get
Notice the numbers are divided into two sections: numbers larger than the last element of the array and numbers smaller than it. The minimum element is at the boundary between the two sections.
We can apply a filter of < the last element
and get the boolean array that characterizes the two sections.
Now the problem is yet again reduced to finding the first true
element in a boolean array. And we already know how to do this from Find Boundary module.
1 | 1 |
| |
2 | 2 | ||
3 | 3 |
| |
4 | - |
| |
4 | + |
| |
5 | - |
| |
5 | + |
| |
6 | 6 | ||
7 | 7 | ||
8 | + |
| |
9 | + |
| |
10 | + |
| |
11 | + |
| |
12 | + |
| |
13 | + |
| |
14 | + |
| |
15 | + |
| |
16 | + | ||
17 | + |
| |
18 | + | ||
8 | 19 |
| |
9 | 20 |
| |
10 | 21 |
| |
11 | 22 |
|