Find Minimum in Rotated Sorted Array

Prereq: Vanilla Binary Search and Finding Boundary with Binary Search

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.

Time Complexity: O(log(n))

1
1
from typing import List
2
2
3
3
def find_min_rotated(arr: List[int]) -> int:
4
-
    # WRITE YOUR BRILLIANT CODE HERE
4
+
    left, right = 0, len(arr) - 1
5
-
    return 0
5
+
    boundary_index = -1
6
6
7
7
8
+
    while left <= right:
9
+
        mid = (left + right) // 2
10
+
        # if <= last element, then belongs to lower half
11
+
        if arr[mid] <= arr[-1]:
12
+
            boundary_index = mid
13
+
            right = mid - 1
14
+
        else:
15
+
            left = mid + 1
16
+
17
+
    return boundary_index
18
+
8
19
if __name__ == '__main__':
9
20
    arr = [int(x) for x in input().split()]
10
21
    res = find_min_rotated(arr)
11
22
    print(res)