In this approach, the task is broken into three main steps:
arr[i] > arr[i+1] and arr[i] > arr[i-1].Time Complexity: O(log n) for peak finding and 2 * O(log n) for the two binary searches.
Total: O(log n).
Space Complexity: O(1) because we use a constant amount of space.
1#include <stdio.h>
2
3// Forward declaration of the MountainArray API.
4// You don't need to implement this interface, it is provided by the problem constraints.
5struct MountainArray {
6 int (*get)(struct MountainArray*, int index);
7 int (*length)(struct MountainArray*);
8};
9
10int findPeakIndex(struct MountainArray* mountainArr) {
11 int left = 0;
12 int right = mountainArr->length(mountainArr) - 1;
13 while (left < right) {
14 int mid = left + (right - left) / 2;
15 if (mountainArr->get(mountainArr, mid) < mountainArr->get(mountainArr, mid + 1)) {
16 left = mid + 1;
17 } else {
18 right = mid;
19 }
20 }
21 return left;
22}
23
24int binarySearch(struct MountainArray* mountainArr, int start, int end, int target, int isAscending) {
25 while (start <= end) {
26 int mid = start + (end - start) / 2;
27 int value = mountainArr->get(mountainArr, mid);
28 if (value == target) {
29 return mid;
30 }
31 if (isAscending) {
32 if (value < target) {
33 start = mid + 1;
34 } else {
35 end = mid - 1;
36 }
37 } else {
38 if (value > target) {
39 start = mid + 1;
40 } else {
41 end = mid - 1;
42 }
43 }
44 }
45 return -1;
46}
47
48int findInMountainArray(int target, struct MountainArray* mountainArr) {
49 int peak = findPeakIndex(mountainArr);
50 int index = binarySearch(mountainArr, 0, peak, target, 1);
51 if (index != -1) {
52 return index;
53 }
54 return binarySearch(mountainArr, peak + 1, mountainArr->length(mountainArr) - 1, target, 0);
55}This C implementation is efficient as it implements a binary search method to find the peak in O(log n) time. After finding the peak, it searches both halves of the mountain array for the target using two separate binary searches. One binary search is for the increasing part (left of the peak) with an increasing order binary search, and another one in the decreasing half (right of the peak) with a decreasing order binary search. As it is a binary search, each takes O(log n) time.
This approach involves directly accessing each element linearly until the condition is satisfied (even though this is not allowed by the problem constraints). It is less optimal and efficient compared to the above implementations, requiring traversal of the entire array.
Time Complexity: O(n) as each element could potentially be checked once.
Space Complexity: O(1) as no extra space is used except for variables.
1class MountainArray {
2 get(index) {
3 // Returns the element of the array at index 'index'.
4 }
5
6 length() {
7 // Returns the number of elements in the mountain array.
8 }
9}
10
11class Solution {
12 findInMountainArray(target, mountainArr) {
13 let len = mountainArr.length();
14 for (let i = 0; i < len; i++) {
15 if (mountainArr.get(i) === target) {
16 return i;
17 }
18 }
19 return -1;
20 }
21}Using JavaScript's brute-force search, the solution deploys a for loop to walk through each element of the mountain array. It checks for a match with the target element, returning the index if found, or -1 after scanning the full array, making it less favorable for large inputs due to its lengthy evaluation process.