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 <stdio.h>
2
3int findPeakElement(int* nums, int numsSize) {
4 int left = 0, right = numsSize - 1;
5 while (left < right) {
6 int mid = left + (right - left) / 2;
7 if (nums[mid] > nums[mid + 1]) {
8 right = mid;
9 } else {
10 left = mid + 1;
11 }
12 }
13 return left;
14}
15
16int main() {
17 int nums[] = {1, 2, 3, 1};
18 int index = findPeakElement(nums, 4);
19 printf("Peak element index: %d\n", index);
20 return 0;
21}This C code performs a binary search on the array 'nums'. We start from the whole array and keep reducing the search space. If nums[mid] is greater than nums[mid+1], we search in the left half since a peak might be possible on the left. Otherwise, we search in the right half. This continues until 'left' equals 'right' and we find the peak.
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)
1function
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.