[LeetCode]Find Peak Element

还是二分，这里考察的是二分的条件不一定是由lo, mid或者hi来决定的。比如在这一题中我们只根据lo, mid和hi的关系来二分的话。比如当我们发现num[lo] >= num[mid]的时候，我们可以确定[lo, mid)是一定存在peak的，但是如果num[lo] < num[mid]也不能证明没有，如果这个时候我们去(mid, hi]去找的话也是有可能找不到的。这样的二分不一定能找出正确答案。这里我们考虑mid和相邻的两个元素left，right：

• 如果mid就是peak，返回peak
• 如果mid是bottom，随意两个区间都有peak，随意去哪一个
• 如果从left到right时递增，(mid, hi]必然有peak
• 如果从left到right时递减，[lo, mid)必然有peak

值得记住的是二分的条件可以取决于其他变量，不要让lo,mid和hi限制思维。还有负无穷和正无穷不能用int max和min来代替，对于这个题某些情况下是会出现问题的。对于其他的题目可能出现问题可能不会出现问题，具体分析。这里我们特殊处理。

代码如下：

	public class Solution {
	public int findPeakElement(int[] num) {
	if (num == null)
	return -1;
	int len = num.length;
	int lo = 0, hi = len - 1;
	while (lo < hi) {
	int mid = lo + (hi - lo) / 2;
	//null represent -∞
	Integer left = mid - 1 < 0? null: num[mid - 1];
	Integer right = mid + 1 > len - 1? null: num[mid + 1];
	if ((left == null || num[mid] > left) && (right == null || num[mid] > right))
	return mid;
	else if ((left == null || num[mid] > left) && (right != null && num[mid] < right))
	lo = mid + 1;
	else
	hi = mid - 1;
	}
	return lo;
	}
	}

view raw find peak.java hosted with ❤ by GitHub