Find Minimum in Rotated Sorted Array

You are given a rotated sorted array which may contain duplicate elements. A rotated sorted array is obtained by taking an originally sorted array \(A = [a_0, a_1, \dots, a_{n-1}]\) and moving a prefix from the beginning to the end, resulting in \(A' = [a_k, a_{k+1}, \dots, a_{n-1}, a_0, a_1, \dots, a_{k-1}]\) for some unknown index \(k\). Your task is to find the minimum element in this array using an algorithm faster than \(O(n)\) in average case.

inputFormat

The input is given from standard input (stdin) in two lines. The first line contains an integer \(n\), the number of elements in the array. The second line contains \(n\) space-separated integers representing the rotated sorted array.

outputFormat

Output the minimum element found in the array to standard output (stdout).

7
4 5 6 7 0 1 2

0