你给出一个整数数组(size为n),其具有以下特点:
- 相邻位置的数字是不同的
- A[0] < A[1] 并且 A[n - 2] > A[n - 1]
假定P是峰值的位置则满足A[P] > A[P-1]
且A[P] > A[P+1]
,返回数组中任意一个峰值的位置。
注意事项
- It's guaranteed the array has at least one peak.
- The array may contain multiple peeks, find any of them.
- The array has at least 3 numbers in it.
样例
给出数组[1, 2, 1, 3, 4, 5, 7, 6]
返回1
, 即数值 2 所在位置, 或者6
, 即数值 7 所在位置.
使用递归思想,每次搜索范围减半
1 int findPeak(vector<int>& A) { 2 // write your code here 3 int low =0; 4 int high=A.size(); 5 int mid; 6 while(high>low){ 7 mid=(low+high)/2; 8 if(A[mid]>A[mid-1] && A[mid]>A[mid+1]){ 9 return mid; 10 } 11 else if(A[mid-1]>A[mid]){ 12 high=mid; 13 } 14 else{ 15 low=mid; 16 } 17 } 18 }