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)
1using System;
2
3public class PeakElementFinder {
4 public static int FindPeakElement(int[] nums) {
5 int left = 0, right = nums.Length - 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
17 public static void Main() {
18 int[] nums = {1, 2, 3, 1};
19 int index = FindPeakElement(nums);
20 Console.WriteLine($"Peak element index: {index}");
21 }
22}This C# code is executing a binary search to locate a peak element. The code utilizes the 'while' loop to continuously adjust the search bounds until the peak element index is determined.
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.