??寻找山型数组的顶点（Maximum Number in Mountain Sequence）
lintcode：题号——585，难度——medium
??给定包含n 个整数的山脉数组，即先增后减的序列，找到山顶（最大值），数组严格递增、严格递减。
??样例1：
输入：nums = [1, 2, 4, 8, 6, 3]
输出：8
??样例2：
输入：nums = [10, 9, 8, 7]
输出：10
??需要在一个先增后减的序列中寻找顶点值，类似爬山的过程，只要一直向上爬，顶点就在前面，身后的路不可能存在顶点，可以通过不断地抛掉一些区间，来缩小目标范围。
??之前的题目——第一个坏的版本[1]中，提到过二分法可以解决形如“ooooxxxx”的问题，本题无法将问题转化为这种形式，需要从另一个方面来思考，可以将整体拆解成“half half”型的两半，抛掉其中一半来缩小目标区间。
??使用二分法，取中点，如果中点是从左向右递增，则可以看成从左向右爬山，当前位置的左边则不可能存在顶点，抛掉左边区间；换个方向，如果中点是从右向左递增，则可以看成是从右向左爬山，当前位置的右边不可能存在顶点，抛掉右边区间。
- 取中点；
- 比较中点与下一个点的关系是递增还是递减，以此来判断顶点在哪一半区间；
- 抛掉不可能存在顶点的区间。
- 继续对剩下的区间执行以上步骤，直到找到顶点。
??过程中需要判断当前点的下一步是在向上走还是向下走，考虑下一个元素的时候可能会越界，套用之前的经典二分搜索模板[2]，则可以不用考虑下一个元素是否越界的问题，因为start或mid之后一定存在end，退出条件是start + 1 < end不会出现访问越界的情况。
??算法的时间复杂度为O(log n)。
??算法的空间复杂度为O(1)。
??注意事项：
返回的是值，不是序号；
??C++版本：
/**
* @param nums: 参数
* @return: 返回值
*/
int findMin(vector<int> &nums) {
int mountainSequence(vector<int> &nums) {
// write your code here
if (nums.empty())
{
return -1;
}
int start = 0;
int end = nums.size() - 1;
int mid = 0;
while (start + 1 < end)
{
mid = start + (end - start) / 2;
if (nums.at(mid) < nums.at(mid + 1))
{
start = mid;
}
if (nums.at(mid) > nums.at(mid + 1))
{
end = mid;
}
}
if (nums.at(start) > nums.at(end))
{
return nums.at(start);
}
else
{
return nums.at(end);
}
}
}
10 寻找山型数组的顶点（Maximum Number in Mountain Sequence）
原文：https://www.cnblogs.com/seedoubleu/p/15042135.html