```
/** Solution1. Non-Recusive. time = O(lgN); space = O(1)
Peak Element nums[i]: (greater than its previous/follefting nodes)
nums[i - 1] < nums[i] > nums[i + 1]
The recursive solution is clearer to show how this method works:
1) Original: left.....mid1 mid2....right
2) Compare to choose the greater one from mid1/mids:
if nums[mid1] > nums[mid2], select left...mid1
if nums[mid1] <= nums[mid2], select mid2...right
3) keep going ..
4) Termination case: left == right, which means we find the element we want
*/
// Because there's no duplication, so any point only have two possibilities: on upward or downward wave.
func findPeakElement(_ nums: [Int]) -> Int {
if nums.count <= 0 {
return 0
}
var mid1 = 0, left = 0, right = nums.count - 1
while left < right {
mid1 = (left + right) / 2
let mid2 = mid1 + 1
if nums[mid1] > nums[mid2] {//less than previous, on the down wave.
right = mid1
} else if (nums[mid1] < nums[mid2]) {//less than following, on the up wave.
left = mid2
}
}
return left
}
/** Solution2. Recursive. = O(lgN); space = O(n) - system stack
*/
func findPeakElement_Recursive(_ nums: [Int]) -> Int {
return helper(nums, 0, nums.count - 1)
}
func helper(_ nums:[Int], _ left: Int, _ right: Int) -> Int {
if left == right {// Termination case
return left
}
let mid1 = (left + right) / 2
let mid2 = mid1 + 1
if nums[mid1] > nums[mid2] {
return helper(nums, left, mid1)
} else {
return helper(nums, mid2, right)
}
}
```