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)
1#include <iostream>
2#include <vector>
3
4int findPeakElement(std::vector<int>& nums) {
5 int left = 0, right = nums.size() - 1;
6 while (left < right) {
7 int mid = left + (right - left) / 2;
8 if (nums[mid] > nums[mid + 1]) {
9 right = mid;
10 } else {
11 left = mid + 1;
12 }
13 }
14 return left;
15}
16
17int main() {
18 std::vector<int> nums = {1, 2, 3, 1};
19 int index = findPeakElement(nums);
20 std::cout << "Peak element index: " << index << std::endl;
21 return 0;
22}This C++ code uses the binary search algorithm in a similar way to the C code implementation. The vector class from the C++ standard library is used to store the elements and perform the search operation.
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.