[F 外商面試考題] Find Peak Element

題目

給定一個字串，找到大於左右兩邊的數字，例如 s = [1,2,1,3,5,6,4] ，答案是 6，因為大於左邊的 5 跟右邊的4

思路

一次 iterate 到底，複雜度是 O(n)，要做到優化 O(logN) 必須用「 binary search 」

參考下圖 step，透過 binary search 找碴看，left 跟 right 交叉時就代表找到 peak element

程式碼

class Solution {
    
    func findPeakElement(_ nums:[Int]) -> Int {                
        var left = 0
        var right = nums.count - 1
        
        while left < right {
            
            var mid = (left + right) / 2
            if nums[mid] < nums[mid + 1] {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left
    }
}