给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
示例 1:
输入: nums = [1,2,3,1] 输出: 2 解释: 3 是峰值元素，你的函数应该返回其索引 2。 示例 2:
输入: nums = [1,2,1,3,5,6,4] 输出: 1 或 5 解释: 你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。 说明:
你的解法应该是 O(logN) 时间复杂度的。
第一次做二分题，思路直接错误。 错点：递归函数结束的条件应该是left > right。我错误写成了函数越界right < 0 || left > nums.size() - 1
思路：用二分法暴力枚举每一个元素。感觉和遍历没什么区别。又麻烦还不符合题意。
class Solution { private: int digit; public: int findMid(int left, int right, vector<int>& nums) { if (left > right) return -1; int mid = (left + right) / 2; if (mid - 1 >= 0 && mid + 1 <= nums.size() - 1) { if (nums[mid - 1] < nums[mid] && nums[mid + 1] < nums[mid]) { return mid; } } else { if (mid - 1 == -1 && mid + 1 == nums.size()) return mid; else if (mid - 1 == -1) { if (nums[mid] > nums[mid + 1]) return mid; } else if (mid + 1 == nums.size()) if (nums[mid] > nums[mid - 1]) return mid; } return findMid(mid + 1, right, nums) == -1 ? findMid(left, mid - 1, nums) : findMid(mid + 1, right, nums); } int findPeakElement(vector<int>& nums) { int left = 0, right = nums.size() - 1; return findMid(left, right, nums); }; };重新思考：如果存在nums[mid] > nums[mid + 1]，那么峰值的序号肯定在mid左边。
证：如果mid左边的序列是递增序列，那么0号元素一定是峰值。如果是递减序列，那么mid就是峰值。如果分段递增递减，则一定会有峰值，且峰值序号位于0和mid之间。
反之，如果nums[mid] < nums[mid + 1],那么峰值肯定在mid + 1右边
这样是[left, right]区间不断缩小，当left == right时，即为正确答案
注意：与nums[mid]与nums[mid + 1]比较和nums[mid]和nums[mid - 1]比较是不一样的。因为(left + right) / 2是向下取整，即整个递归（循环）过程中，mid + 1不会越界。但是mid - 1会越界。所以如果与mid - 1比较，需要改成（left + right) / 2 + 1.
class Solution { public: int findMid(int left, int right, vector<int>& nums) { if (left == right) return left; int mid = (left + right) / 2; if (nums[mid] > nums[mid + 1]) { return findMid(left, mid, nums); } else { return findMid(mid + 1, right, nums); } } int findPeakElement(vector<int>& nums) { return findMid(0, nums.size() - 1, nums); }; };