还是二分，这里考察的是二分的条件不一定是由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来代替，对于这个题某些情况下是会出现问题的。对于其他的题目可能出现问题可能不会出现问题，具体分析。这里我们特殊处理。
代码如下：
No comments:
Post a Comment