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)
1def findPeakElement(nums):
2 left, right = 0, len(nums) - 1
3 while left < right:
4 mid = (left + right) // 2
5 if nums[mid] > nums[mid + 1]:
6 right = mid
7 else:
8 left = mid + 1
9 return left
10
11nums = [1, 2, 3, 1]
12index = findPeakElement(nums)
13print(f"Peak element index: {index}")This Python solution employs a binary search method. The 'while' loop continues until the search space is reduced to a single element. We adjust either the 'right' or 'left' index by evaluating the mid-element and its right neighbor
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 JavaScript solution uses a for loop to check each element for the peak property. It's a viable option for small datasets but does not take advantage of binary search speed.