Swift 3.0

//
//  M_153_FindMinimuminRotatedSortedArray.swift
//  AlgorithmLeetCode
//
//  Created by okerivy on 2017/3/8.
//  Copyright ? 2017年 okerivy. All rights reserved.
//  https://leetcode.com/problems/find-minimum-in-rotated-sorted-array

import Foundation


// MARK: - 題目名稱: 153. Find Minimum in Rotated Sorted Array

/* MARK: - 所屬類別:
 標(biāo)簽: Array, Binary Search
 
 相關(guān)題目:
  (M) Search in Rotated Sorted Array
  (H) Find Minimum in Rotated Sorted Array II
 
 */

/* MARK: - 題目英文:
 
 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
 
 (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
 
 Find the minimum element.
 
 You may assume no duplicate exists in the array.
 
 */


/* MARK: - 題目翻譯:
 
 假設(shè)將一個(gè)排好序的數(shù)組以某個(gè)你不知道的軸旋轉(zhuǎn)皆尔。(例如： 0 1 2 4 5 6 7 可能變成 4 5 6 7 0 1 2)校哎。 
 找到數(shù)組中最小的元素檐涝。
 你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
 
 */



/* MARK: - 解題思路:
 
 // 1.二分查找
 這題要求在一個(gè)輪轉(zhuǎn)了的排序數(shù)組里面找到最小值方灾，我們可以用二分法來(lái)做。
 
 首先我們需要知道，對(duì)于一個(gè)區(qū)間A柬批，如果A[start] < A[stop]顷扩，那么該區(qū)間一定是有序的了拐邪。
 
 假設(shè)在一個(gè)輪轉(zhuǎn)的排序數(shù)組A，我們首先獲取中間元素的值隘截，A[mid]扎阶，mid = (start + stop) / 2。因?yàn)閿?shù)組沒(méi)有重復(fù)元素婶芭，那么就有兩種情況：
 
 A[mid] > A[start]东臀，那么最小值一定在右半?yún)^(qū)間，譬如[4,5,6,7,0,1,2]犀农，中間元素為7惰赋，7 > 4，最小元素一定在[7,0,1,2]這邊呵哨，于是我們繼續(xù)在這個(gè)區(qū)間查找赁濒。
 A[mid] < A[start]，那么最小值一定在左半?yún)^(qū)間孟害，譬如[7,0,1,2,4,5,6]拒炎，這件元素為2，2 < 7挨务，我們繼續(xù)在[7,0,1,2]這個(gè)區(qū)間查找击你。

 // 2. 遍歷查找
 遍歷當(dāng)前數(shù)組元素玉组，如果當(dāng)前元素比它之后的一個(gè)元素大，說(shuō)明這個(gè)地方是發(fā)生旋轉(zhuǎn)的地方丁侄。
 后一個(gè)元素就是最小的元素球切。
 思路非常簡(jiǎn)單，完整代碼如下所示：
 
 */


// FIXME: 沒(méi)有完成
/* MARK: - 復(fù)雜度分析:
 
 二分查找 時(shí)間 O(N) 空間 O(N) 
 遍歷重找
 
 */


// MARK: - 代碼:
private class Solution {
    
    // 二分查找
    func findMin(_ nums: [Int]) -> Int {
        
        // 對(duì) size <= 2的情況直接判斷
        let size = nums.count
        if size == 0 {
            return 0
        } else if size == 1 {
            return nums[0]
        } else if size == 2 {
            return min(nums[0], nums[1])
        }
        
        var start = 0
        var stop = size - 1
        
        while  start < stop  {
            if nums[start] < nums[stop] {
                return nums[start]
            }
            
            // mid 肯定 > 1
            let mid = (start + stop)/2
            // mid == start 證明已經(jīng)找到 肯定會(huì)來(lái)到這里的 結(jié)束循環(huán)
            if mid == start  {
                break
            }
            
            // A[mid] > A[start]绒障，那么 證明 左半邊是有序的, 那么最小值一定在右半?yún)^(qū)間
            if nums[mid] > nums[start] {
                start = mid
                
                // A[mid] < A[start]吨凑，那么 證明 左半邊是無(wú)序的, 那么最小值一定在左半?yún)^(qū)間
            } else if  nums[mid] < nums[start] {
                stop = mid
            }
        }
        
        // 返回最小值, 這個(gè)時(shí)候 start 和 stop 差值不會(huì)大于 1
        return min(nums[start], nums[stop])
    }
    

    
    
    // 遍歷查找
    func findMin2(_ nums: [Int]) -> Int {
        
        // 返回值為 Int? 用來(lái) 返回nil
        if nums.count <= 0 {
            return 0
        }
        
        for i in 0 ..< nums.count - 1 {
            
            if nums[i] > nums[i + 1] {
                return nums[i + 1]
            }
            
        }
        
        return nums[0]
    }
    
}


// MARK: - 測(cè)試代碼:
func findMinimuminRotatedSortedArray() {
    
    var nums1 = [Int]()
    nums1 = [4,5,6,7,0,1,2]
    
    print(Solution().findMin(nums1))
    
    print(nums1)
}