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
In this approach, we first handle edge cases for the start and end of the array. Then, we iterate through the array to find the first element greater than its neighbors. While the time complexity is O(n), it provides a straightforward implementation.