# O(logN) Solution JavaCode

• This problem is similar to Local Minimum. And according to the given condition, num[i] != num[i+1], there must exist a O(logN) solution. So we use binary search for this problem.

• If num[i-1] < num[i] > num[i+1], then num[i] is peak
• If num[i-1] < num[i] < num[i+1], then num[i+1...n-1] must contains a peak
• If num[i-1] > num[i] > num[i+1], then num[0...i-1] must contains a peak
• If num[i-1] > num[i] < num[i+1], then both sides have peak
(n is num.length)

Here is the code

``````public int findPeakElement(int[] num) {
return helper(num,0,num.length-1);
}

public int helper(int[] num,int start,int end){
if(start == end){
return start;
}else if(start+1 == end){
if(num[start] > num[end]) return start;
return end;
}else{

int m = (start+end)/2;

if(num[m] > num[m-1] && num[m] > num[m+1]){

return m;

}else if(num[m-1] > num[m] && num[m] > num[m+1]){

return helper(num,start,m-1);

}else{

return helper(num,m+1,end);

}

}
}``````

• This post is deleted!

if(start == end)
return start;

array is not sorted, how do you get correct answer for say. 0 1 2 3 0

• start, end is the index, start ==end means there is only one element.

• ok, i mis-read it, thanks!

• So when peak at both side, just go to right side?

• I was cheated by you.haha

• Choose any side does not matter. Any peak is Ok as per the Question description.

• the statement "If num[i-1] > num[i] > num[i+1], then num[0...i-1] must contains a peak" doesn't apply on test case [7, 6, 5, 3, 2, 5, 4].

• 7 is the peak here (applicable as per question)..

• thanks, great solution!

• Great solution! Accroding to your code , I write another program that return the bottom element of the list.

``````public int findBottomElement(int[] num, int left, int right) {
if (left == right) {
return left;
} else if (left + 1 == right) {
if (num[left] < num[right]) {
return left;
}
return right;
} else {
int mid = (left + right) / 2;
if (num[mid] < num[mid+1] && num[mid] < num[mid-1]) {
return mid;
} else if (num[mid] < num[mid+1] && num[mid] > num[mid-1]) {
return findBottomElement(num, left, mid-1);
} else {
return findBottomElement(num, mid+1, right);
}
}
}

public int findBottomElement(int[] num) {
int left = 0, right = num.length - 1;
return findBottomElement(num, left, right);
}``````

• My Iterative code with similar idea.

``````public class Solution {
public int findPeakElement(int[] nums) {
int lo = 0, hi = nums.length-1;
while(lo < hi){
if(lo +1== hi)
return nums[lo] > nums[hi]? lo : hi;
int mid = lo + (hi - lo)/2;
if(nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1])
return mid;
else if(nums[mid] > nums[mid-1] && nums[mid] < nums[mid+1])
lo = mid+1;
else
hi = mid-1;
}
return lo;
}
``````

}

• Great solution! Can you tell me why "num[i] != num[i+1], there must exist a O(logN) solution."?

• @xctom Hi please check output for this case:[1,0,2,3,4,5,6]

• This code doesn't work for the input "[3,2,2,2,1]".

• @rohitkgp if there is only 1 element, return start

• This code doesn't work for the input "[3,2,2,2,1]".

There wouldn't be same numbers next to each other because of the specification of the question.

• smart solution.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.