Find Minimum in Rotated Sorted Array

You are given a rotated sorted array that may contain duplicates. A rotated sorted array is obtained by taking a sorted array \( S = [s_1, s_2, \dots, s_n] \) and rotating it at some pivot index so that the array becomes \( [s_{k+1}, s_{k+2}, \dots, s_n, s_1, s_2, \dots, s_k] \) for some \( 0 \le k < n \). Your task is to find the minimum element in this array.

The solution should be efficient; ideally using a modified binary search approach that achieves better than \( O(n) \) average complexity.

Input/Output: The program will receive input via standard input (stdin) and must print the result to standard output (stdout).

inputFormat

The first line contains an integer \( n \) indicating the number of elements in the array. The second line contains \( n \) space-separated integers representing the rotated sorted array.

outputFormat

Output a single integer representing the minimum element in the array.

7
4 5 6 7 0 1 2

0