Sponsored
Sponsored
The binary search approach is used to achieve the O(log n) time complexity. Binary search leverages the idea that if an element is not a peak and is less than its right neighbor, then a peak must exist on the right half of the array. Similarly, if it is less than its left neighbor, a peak must exist on the left half of the array. Thus, we keep narrowing down the search window until we find a peak.
Time Complexity: O(log n), Space Complexity: O(1)
1function findPeakElement(nums) {
2 let left = 0, right = nums.length - 1;
3 while (left < right) {
4 let mid = Math.floor((left + right) / 2);
5 if (nums[mid] > nums[mid + 1]) {
6 right = mid;
7 } else {
8 left = mid + 1;
9 }
10 }
11 return left;
12}
13
14const nums = [1, 2, 3, 1];
15const index = findPeakElement(nums);
16console.log(`Peak element index: ${index}`);This JavaScript solution uses binary search logic in a similar fashion to other implementations. We utilize Math.floor for dividing by 2 to ensure we get a proper mid index, and adjust the search bounds based on comparisons.
Though not adhering to the O(log n) requirement, a linear scan is straightforward. It involves checking each element to see if it is a peak element, which can serve as a quick solution, but not fulfilling the constraints in a theoretical context. Practically, it can be used in scenarios where constraints are more relaxed or strictly linear approaches are preferred.
Time Complexity: O(n), Space Complexity: O(1)
1
This Python solution iterates over the list from the second to the second-last element checking if they qualify as a peak. The linear scan makes this a practical yet less optimal choice for peak finding.