[C++]LeetCode: 118 Find Peak Element (二分查找寻找数组局部峰值)

浏览数：60 / 时间：2015年06月08日

题目：

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.

click to show spoilers.

Note:

Your solution should be in logarithmic complexity.

思路：这道题如果不用二分查找，时间复杂度是O(N)，我们需要遍历一遍数组，找到第一个元素，它大于其后续的其他元素，就是局部峰值。题目中要求在对数时间内完成查找，我们考虑使用二分查找。如果中间元素大于其相邻的后续元素，则中间元素左侧（包括中间元素）必然包含一个局部最大值，如果中间元素小于其相邻的后续元素，则中间元素右侧必然包含一个局部最大值。直到最后左边沿和右边沿相遇，我们找到所求峰值。

我们选择左右边沿相遇作为结束条件，以及只和后续元素mid+1比较，可以避免考虑当mid为0时，mid-1为负值的特殊情况。题目中只是让我们假设num[-1] = num[n] = 负无穷，实际上，数组是无法得到这两个值的，指针会越界。

这里，我们还需要注意的是，当中间元素大于其相邻的后续元素时，说明中间元素左侧（包含中间元素）必然包含一个局部最大值，这时，中间元素也可能是峰值点，所以移动时，end = mid, 而不能跨过中间元素end = mid -1. 而相反情况，中间元素小于其向相邻后续元素，则中间元素右侧比包含一个局部最大值，这时候中间元素一定不是局部最大点，start = mid + 1.

复杂度：O(lg(n))

AC Code:

class Solution {
public:
    int findPeakElement(const vector<int> &num) {
        if(num.size() == 0) return 0;
        
        int start = 0;
        int end = num.size() - 1;
        
        while(start <= end)
        {
            if(start == end) return start;
            
            int mid = start + (end - start) / 2;
            
            if(num[mid] < num[mid+1])
            {
                start = mid + 1;
            }
            else
            {
                end = mid;
            }
        }
    }
};

等做完二分查找的所有题后，可以总结一下这类题的特点，以及二分查找的所有应用情况。

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

[C++]LeetCode: 118 Find Peak Element (二分查找寻找数组局部峰值)