剑指Offer算法题-旋转数组的最小数字--Swift

题目：把一个数组最开始的若干个元素搬到数组的尾部，我们称之为数组的旋转。输入一个递增数组的旋转，输出旋转数组的最小元素。例如，数组{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）

func minInOrder<T:Comparable>(rotationArray:Array<T>) -> T? {
    var minItem = rotationArray.first
    for item in rotationArray {
        if minItem! > item {
            minItem = item
        }
    }
    return minItem
}

方案二代码 （swift）

func min<T:Comparable>(rotationArray:Array<T>) -> T? {
    if rotationArray.count < 1 {
        return nil
    }
    var aheadIndex = 0
    var tailIndex = rotationArray.count - 1
    //先让中间指向头部，是因为如果头部元素如果小于尾部元素，则证明旋转了0个元素，此时头部元素等于最小值
    var middleIndex = aheadIndex
    while rotationArray[aheadIndex] >=  rotationArray[tailIndex]{
        if(tailIndex - aheadIndex == 1) {
            middleIndex = tailIndex
            break
        }
        //此处不要写成(aheadIndex + tailIndex) / 2，因为这么写，当数组元素比较多时，可以会造成溢出问题
        middleIndex = aheadIndex + (tailIndex - aheadIndex) / 2
        if rotationArray[aheadIndex] == rotationArray[tailIndex] && rotationArray[aheadIndex] == rotationArray[middleIndex] {
        //把P1到P2之间的元素，重新生成一个新数组，然后调用方案一的写法
            return minInOrder(rotationArray: Array(rotationArray[aheadIndex...tailIndex]))
        }
        if rotationArray[middleIndex] >= rotationArray[aheadIndex] {
            aheadIndex = middleIndex
        }else if rotationArray[middleIndex] <= rotationArray[tailIndex] {
            tailIndex = middleIndex
        }
    }
    return rotationArray[middleIndex]
}