你给出一个整数数组(size为n)，其具有以下特点：
- 相邻位置的数字是不同的
- A[0] < A[1] 并且 A[n - 2] > A[n - 1]
假定P是峰值的位置则满足A[P] > A[P-1]且A[P] > A[P+1]，返回数组中任意一个峰值的位置。
样例
给出数组[1, 2, 1, 3, 4, 5, 7, 6]返回1, 即数值 2 所在位置, 或者6, 即数值 7 所在位置.
题意实际应该是找任意一个极大值
class Solution: """ @param: A: An integers array. @return: return any of peek positions. """ def findPeak(self, A): # write your code here if len(A)<2: return A
for i in range(1,len(A)-1): if (A[i+1]-A[i]) < 0: return i
时间复杂度O(n)，Time Limit Exceeded
考虑二分法，九章参考：
class Solution: #@param A: An integers list. #@return: return any of peek positions. def findPeak(self, A): # write your code here start, end = 1, len(A) - 2 while start + 1 < end: mid = (start + end) / 2 if A[mid] < A[mid - 1]: end = mid elif A[mid] < A[mid + 1]: start = mid else: end = mid #直接return mid就行，不用再找了 if A[start] < A[end]: return end else: return start
一开始觉得不对，仔细审题发现还有约束
- A[0] < A[1] 并且 A[n - 2] > A[n - 1]
只用考虑中间点局部范围则可以找到某峰值的区间。