# Find the maximum by binary search (recursion and iteration)

• Consider that each local maximum is one valid peak.
My solution is to find one local maximum with binary search.
Binary search satisfies the O(logn) computational complexity.

Binary Search: recursion

``````class Solution {
public:

int findPeakElement(const vector<int> &num) {
return Helper(num, 0, num.size()-1);
}
int Helper(const vector<int> &num, int low, int high)
{
if(low == high)
return low;
else
{
int mid1 = (low+high)/2;
int mid2 = mid1+1;
if(num[mid1] > num[mid2])
return Helper(num, low, mid1);
else
return Helper(num, mid2, high);
}
}
};
``````

Binary Search: iteration

``````class Solution {
public:
int findPeakElement(const vector<int> &num)
{
int low = 0;
int high = num.size()-1;

while(low < high)
{
int mid1 = (low+high)/2;
int mid2 = mid1+1;
if(num[mid1] < num[mid2])
low = mid2;
else
high = mid1;
}
return low;
}
};
``````

Sequential Search:

``````class Solution {
public:
int findPeakElement(const vector<int> &num) {
for(int i = 1; i < num.size(); i ++)
{
if(num[i] < num[i-1])
{// <
return i-1;
}
}
return num.size()-1;
}
};``````

• That sequential search is really wise!

• Is that right? correct me if I'm wrong, but what about the case [2,4,1,3,6]?

• in your case, 6 is the peak, its left is 3, its right is -oo

• can this algorithm find absolute maximum? what if the array is [9, 4, 6, 8, 1, 7]? It seems the index found is 5 which is element 7 though this is qualified as peak element.

• This post is deleted!

• Thank you for your attention. In fact, every local maximum is one valid peak. Thus I said in the first sentence "Consider that the sequence has only one peak."

• Ah, I see. Thanks.

• This post is deleted!

• Very brilliant, but I don't think saying "Consider that the sequence has only one peak. The problem equals to finding the maximum. " is necessary, because for your solution, it's actually finding the peak instead of finding the maximum, and it happens to be the maximum number because there is only one peak.

• The sequential search is really smart!

• Yes, you're right. My solution is to find one local maximum, which is a valid peak.

• The sequential search seems neat. But it is O(n) not O(logn), isn't it?

• Yes, you're right. I proposed it here just for comparison :)

• This post is deleted!

• How about [1,2,1] in Binary Search: iteration? The code didn't get accepted. I added a condition: if (num[mid1] > num[mid2] and num[mid1]>num[mid-1]) return mid; and then it works. Thanks!

• Thanks, I learned a lot! The Sequential Search is really great!

• This post is deleted!