Swift.旋转数组的最小数字

题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

import Foundation

class For08Solution {
    func findMin(_ n: [Int]) -> Int {
        
        var s = n
        return find(&s, 0, (n.count-1)/2, n.count-1)
        
    }
    
    func find(_ n: inout [Int],_ left: Int,_ mid: Int,_ right: Int) -> Int {
        
        if left == mid {
            return n[right]
        }
        
        if n[left] == n[right] && n[left] == n[mid] {
            return min(n, left, right)
        }
        
        if n[left] > n[mid] {
            return find(&n,left,(left+mid)/2,mid)
        }
        
        if n[mid+1] > n[right] {
            return find(&n,mid+1,(mid+right/2),right)
        }
        
        return n[left] > n[mid+1] ? n[mid+1] : n[left]
    }
    
    
    func min(_ n: [Int],_ left: Int,_ right: Int) -> Int {
        var res = n[left]
        
        var r = left + 1
        
        while r <= right {
            if res > n[r] {
                res = n[r]
            }
            r += 1
        }
        
        return res
    }
}

算法思想：将旋转数组对半分可以得到一个包含最小元素的新旋转数组，以及一个非递减排序的数组。新的旋转数组的数组元素是原数组的一半，从而将问题规模减少了一半，这种折半性质的算法的时间复杂度为 O(logN)
此时问题的关键在于确定对半分得到的两个数组哪一个是旋转数组，哪一个是非递减数组。我们很容易知道非递减数组的第一个元素一定小于等于最后一个元素。

github地址：https://github.com/cubegao/LeetCode