题目：把一个数组最开始的若干个元素搬到数组的尾部，我们称之为数组的旋转。输入一个递增数组的旋转，输出旋转数组的最小元素。例如，数组{3，4，5，1，2}为数组{1，2，3，4，5}的一个旋转，该数组的最小值为 1
方案一
遍历数组，找寻最小值
方案二
旋转之后的数组实际上可以划分为 2 个递增的数组。而且前面的子数组的元素都大于等于后面子数组的元素，并且最小的元素刚好是 2 个子数组的分界点。
我们可以用两个指针分别指向数组的第一个元素记为 P1 和最后一个元素记为 P2，若旋转的个数大于 0,P1 一定是大于等于 P2 的，若旋转的个数等于 0，则 P1 就是最小值。此时先考虑旋转个数大于 0 的情况。
接着我们可以找到数组的 M，如果 M 大于 P1，我们可以认为 M 位于前面的递增数组，则可以把 P1 指向 M，如果 M 小于 P2，我们可以认为 M 位于后面的递增数组，则可以把 P2 指向 M。然后把 M 指向此时 P1 与 P2 的中间，直到 P1 小于 P2 或者 P1 和 P2 的下标相邻
还有一个特殊情况就是 P1=P2=M 时，此时不知道 M 是位于前面的递增数组还是后面的递增数组，就只能遍历 P1 到 P2 之间的值，找到最小值。
方案一代码（swift）
1 | func minInOrder<T:Comparable>(rotationArray:Array<T>) -> T? { |
2 | var minItem = rotationArray.first |
3 | for item in rotationArray { |
4 | if minItem! > item { |
5 | minItem = item |
6 | } |
7 | } |
8 | return minItem |
9 | } |
方案二代码 （swift）
1 | func min<T:Comparable>(rotationArray:Array<T>) -> T? { |
2 | if rotationArray.count < 1 { |
3 | return nil |
4 | } |
5 | var aheadIndex = 0 |
6 | var tailIndex = rotationArray.count - 1 |
7 | //先让中间指向头部，是因为如果头部元素如果小于尾部元素，则证明旋转了0个元素，此时头部元素等于最小值 |
8 | var middleIndex = aheadIndex |
9 | while rotationArray[aheadIndex] >= rotationArray[tailIndex]{ |
10 | if(tailIndex - aheadIndex == 1) { |
11 | middleIndex = tailIndex |
12 | break |
13 | } |
14 | //此处不要写成(aheadIndex + tailIndex) / 2，因为这么写，当数组元素比较多时，可以会造成溢出问题 |
15 | middleIndex = aheadIndex + (tailIndex - aheadIndex) / 2 |
16 | if rotationArray[aheadIndex] == rotationArray[tailIndex] && rotationArray[aheadIndex] == rotationArray[middleIndex] { |
17 | //把P1到P2之间的元素，重新生成一个新数组，然后调用方案一的写法 |
18 | return minInOrder(rotationArray: Array(rotationArray[aheadIndex...tailIndex])) |
19 | } |
20 | if rotationArray[middleIndex] >= rotationArray[aheadIndex] { |
21 | aheadIndex = middleIndex |
22 | }else if rotationArray[middleIndex] <= rotationArray[tailIndex] { |
23 | tailIndex = middleIndex |
24 | } |
25 | } |
26 | return rotationArray[middleIndex] |
27 | } |