Description

我们把一个升序排列的，且不含重复元素的数组，在某个点发生旋转后形成的新数组，叫做原数组的旋转数组。

比如，升序数组0,1,2,4,5,6,7可能变为旋转数组4,5,6,7,0,1,2。

请找出旋转数组中的最小元素。

难度++：你能在线性时间内解决这个问题吗？

PS：二分查找的时间复杂度为O(logn)，线性时间指O(n)。

Input Format

第一行一个整数n，代表数组的长度（1≤n≤100）。

第二行为旋转数组。

Output Format

输出旋转数组中的最小元素。

5
3 4 5 1 2​

1​

Source

基础百练 二分