Click here to see the full article post
Am I missing something? If the array is sorted, then the last element is a peak element, since array[i] !== array [i+1];
So, answer would just be array[array.length - 1] if sorted. That would result in basically O(n)
I'm not sure why the binary search is reliable here since elements in array is not sorted. Let's say nums[mid] < noms[mid + 1], based on the binary search algorithm recursive version, we are looking at range (mid + 1, n - 1), but it is possible that there is a peak in range (0, mid) since it's not sorted array. Can someone help on that? Thanks.
The first solution will give a wrong result for: [1, 7, 5, 3, 6, 6, 7, 2, 4, 5, 8], the result should be 10, whereas it is giving 1, because it is returning at 7 > 5 ? true and the result returned is 1. I do not know what's the logic behind the first approach. Why can't the peak be in the end, or the graphs have multiple valleys?
actually, this question is confusing
we have this condition: num[i] ≠ num[i+1]
it means that any single element is different than its neighbors - this condition guaranteed that the max value of all the elements is the peak (as its neighbors cannot be the same, but it is already the max)
so, we can simply find max value(s) and its index, and return. this also gives O(n) time and O(1) space
The first or the last element are always the peak of the arrays,according to the question.
@SanD array: [1, 7, 5, 3, 6, 6, 7, 2, 4, 5, 8] actually has multiple peaks(7, 7 and 8). Binary search works here because we want to find any peak element which is defined as the element greater than its neighbor elements. We are not trying to find the maximum peak value which would be 8 here.
It seems both the binary search will fail for this case?
[1, 2, 1, 4, 5, 6, 7]
Am I missing something??
oh nevermind, I guess in that case 7 is a peak as well, I was thinking only 2 (index 1) is the only peak...
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.