LeetCode[Array]: Find Peak Element

LeetCode[Array]: 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.
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.

這個題目要求時間復雜度為O(log(N))，可以利用二分查找來做，只是這裡更新搜索區間的時候不太一樣：如果到mid的前一步是上坡而mid的下一步是下坡，那麼mid即是山頂；如果mid的前一步和後一步都是上坡，那麼山頂必然位於後半區間；如果mid的前一步和後一步都是下坡，那麼山頂必然位於前半區間。除此之外，還需要處理邊界問題。

我的C++代碼實現如下：

int findPeakElement(const vector &num) {
    int low = 0, high = num.size() - 1;
    while (low <= high) {
        int mid  = (low + high) >> 1;
        bool isUphillForward = (mid == 0 ? true : num[mid] > num[mid - 1]);
        bool isUphillAfter = (mid == num.size() - 1 ? false : num[mid + 1] > num[mid]);

        if (isUphillForward && !isUphillAfter) return mid;
        else if (isUphillForward && isUphillAfter) low = mid + 1;
        else high = mid - 1;
    }

    return low;
}