[LeetCode]Find Peak Element

因为默认左右两边都是负无穷，所以我们可以肯定一定存在解。并且我们进一步观察得知，nums[0]一定处在上升序列，nums[len - 1]一定处在下降序列，以他们作为lo和hi。我们每次取中间的数能判断其处在上升还是下降序列，按情况移动lo和hi，使得lo永远处在上升序列，hi永远处在下降序列，这样解一直存在于lo和hi当中，时间复杂度O(log n)，代码如下:

	class Solution {
	public:
	int findPeakElement(vector<int>& nums) {
	int len = nums.size(), lo = 0, hi = len - 1;
	while(lo < hi)
	{
	int mid = lo + (hi - lo) / 2;
	if(nums[mid] < nums[mid + 1])
	lo = mid + 1;
	else
	hi = mid;
	}
	return lo;
	}
	};

view raw Find Peak Element.cpp hosted with ❤ by GitHub