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
public class PeakElementFinder {
public static int FindPeakElement(int[] nums) {
int n = nums.Length;
if (n == 1) return 0;
if (nums[0] > nums[1]) return 0;
if (nums[n - 1] > nums[n - 2]) return n - 1;
for (int i = 1; i < n - 1; i++) {
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
return i;
}
}
return -1;
}
public static void Main() {
int[] nums = {1, 2, 3, 1};
int index = FindPeakElement(nums);
Console.WriteLine($"Peak element index: {index}");
}
}This C# method linearly checks each element from the second to the second-last to find a peak, making it simple to implement but not as time-efficient.