[解題筆記] Leetcode#153 — Find Minimum in Rotated Sorted Array

Photo by Chris Ried on Unsplash

不了解Binary Search演算法，可以參考[演算法筆記] Binary Search文章

Problem

題號：Leetcode 153
標題：Find Minimum in Rotated Sorted Array
演算法：Binary Search

Explain

當left值 > right值，表示有rotate；沒有rotate的陣列，預設排序ASC，所以left值 < right值，此時最小值就是陣列第0個元素。

當mid值 > Right值時，最小值在右半部

當mid值 < Right值時，最小值在左半部

Solution

class Solution {
    func findMin(_ nums: [Int]) -> Int {

        var left = 0
        var right = nums.count - 1
        var result = nums[left]

        if nums[left] > nums[right] {
             //The nums has roated n times
             while left <= right {
                let mid = (left+right)/2
                result = min(result, nums[mid])

                if nums[mid] > nums[right] {
                    //當mid值 > Right值時，最小值在右半部
                    left = mid + 1
                } else {
                    //當mid值 < Right值時，最小值在左半部
                    right = mid - 1
                }
            }
        }

        return result
    }
}