There is an integer array which has the following features:
- The numbers in adjacent positions are different.
- A[0] < A[1] & & A[A.length - 2] > A[A.length - 1].
We define a position P is a peek if:
A[P]
>
A[P-1]
&
&
A[P]
>
A[P+1]
Find a peak element in this array. Return the index of the peak.
Notice
The array may contains multiple peeks, find any of them.
Have you met this question in a real interview?
Yes
Example
Given[1, 2, 1, 3, 4, 5, 7, 6]
Return index1
(which is number 2) or6
(which is number 7)
Time complexity O(logN)
class Solution {
public:
/\*\*
\* @param A: An integers array.
\* @return: return any of peek positions.
\*/
int findPeak\(vector<int> A\) {
// write your code here
if \(A.size\(\) < 3\) {
return -1;
}
int start = 0, end = A.size\(\) - 1;
while \(start + 1 < end\) {
int mid = \(end - start\) / 2 + start;
// cout << start << endl;
// cout << end << endl;
// cout << mid << endl;
if \(A\[mid\] > A\[mid - 1\] && A\[mid\] > A\[mid + 1\]\) {
return mid;
}
if \(A\[mid\] < A\[mid + 1\]\) {
start = mid;
} else {
end = mid;
}
}
return -1;
}
};