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#include <vector>
int findPeakElement(std::vector<int>& nums) {
int n = nums.size();
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;
}
int main() {
std::vector<int> nums = {1, 2, 3, 1};
int index = findPeakElement(nums);
std::cout << "Peak element index: " << index << std::endl;
return 0;
}This C++ solution also uses a linear scan to find a peak element. The logic involves checking each element in sequence to see if it is greater than both its neighbors.