1 题目
??寻找峰值（Find Peak Element）
lintcode：题号——75，难度——medium
2 描述
??给定一个整数数组(size为n)，其具有以下特点：相邻位置的数字是不同的；A[0] < A[1] 并且 A[n - 2] > A[n - 1]；假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。数组保证至少存在一个峰；如果数组存在多个峰，返回其中任意一个就行；数组至少包含 3 个数。
??样例1：
输入：A = [1, 2, 1, 3, 4, 5, 7, 6]
输出：1
解释：返回任意一个峰顶元素的下标，元素2的下标为1，下标6也同样正确。
??样例2：
输入：A = [1,2,3,4,1]
输出：3
解释：返回峰顶元素4的下标3。
3 思路
??寻找峰值点，峰值点的特征是点的左边处于递增状态、右边处于递减状态。题中对数组做了一些限定：A[0] < A[1]，即起点是递增状态； A[n - 2] > A[n - 1]，即到达终点时候是递减状态，且相邻位置的数字不同。需要找到数组中的任意一个峰值即可，可以通过递增递减的状态来寻找，即在任意一个区间中，如果起点递增、终点递减，那这个区间内一定有峰值，通过二分法拆分为“half half”的方式，每次留下一定存在峰值的区间，抛掉不一定存在峰值的区间，最后即可找到。
- 取中点；
- 比较中点与下一个点，判断当前处于递增还是递减；
- 找到起点递增、终点递减这样的一定存在峰值的区间，抛掉另一半不一定存在峰值的区间。
- 重复上述过程，直到找到峰值。
3.1 图解
输入：A = [1, 2, 1, 3, 4, 5, 7, 6]
输出：6
解释：返回任意一个峰顶元素的下标即可，峰值元素7的下标为6。
3.2 时间复杂度
??算法的时间复杂度为O(log n)。
3.3 空间复杂度
??算法的空间复杂度为O(1)。
4 源码
??注意事项：
- 最后两个元素中取峰值的时候，在逻辑上可以直接取end。
因为在最后一次缩小区间的时候，必定是end = mid的情况。如果最后一次缩小区间是start = mid的情况，则说明在缩小后的区间内start点还是处于递增的状态，start必定还不是峰值，区间还能再缩。
- 返回的是序号，不是元素值。
??C++版本：
/**
* @param A: 整数数组
* @return: 任意峰值点的下标序号
*/
int findPeak(vector<int> &A) {
// write your code here
if (A.size() < 3)
{
return -1;
}
int start = 0;
int end = A.size() - 1;
int mid = 0;
while (start + 1 < end)
{
mid = start + (end - start) / 2;
if (A.at(mid) < A.at(mid + 1))
{
start = mid;
}
if (A.at(mid) > A.at(mid + 1))
{
end = mid;
}
}
return end;
}