[LeetCode] 162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Note:

Your solution should be in logarithmic complexity.

<Solution>

因為看到題目要求是要 O(logN) 的時間複雜度

所以想到使用 binary search 來做

想法如下

• 當 mid 比右邊的數字小的時候，代表右邊有可能有 peak value，所以將 left = mid + 1

• 反之，則代表左邊可能有 peak value，所以 right = mid

code 如下