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 <iostream>
2#include <vector>
3using namespace std;
4
5// Mockup of MountainArray, simulating interface.
6class MountainArray {
7public:
8 int get(int index) const;
9 int length() const;
10};
11
12int findPeakIndex(const MountainArray &mountainArr) {
13 int left = 0;
14 int right = mountainArr.length() - 1;
15 while (left < right) {
16 int mid = left + (right - left) / 2;
17 if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
18 left = mid + 1;
19 } else {
20 right = mid;
21 }
22 }
23 return left;
24}
25
26int binarySearch(const MountainArray &mountainArr, int start, int end, int target, bool isAscending) {
27 while (start <= end) {
28 int mid = start + (end - start) / 2;
29 int value = mountainArr.get(mid);
30 if (value == target) {
31 return mid;
32 }
33 if (isAscending) {
34 if (value < target) {
35 start = mid + 1;
36 } else {
37 end = mid - 1;
38 }
39 } else {
40 if (value > target) {
41 start = mid + 1;
42 } else {
43 end = mid - 1;
44 }
45 }
46 }
47 return -1;
48}
49
50int findInMountainArray(int target, const MountainArray &mountainArr) {
51 int peak = findPeakIndex(mountainArr);
52 int index = binarySearch(mountainArr, 0, peak, target, true);
53 if (index != -1) {
54 return index;
55 }
56 return binarySearch(mountainArr, peak + 1, mountainArr.length() - 1, target, false);
57}The C++ implementation works similarly to the C solution. It uses binary search to find the peak index and then performs two additional binary searches on both sides of the peak. Finding the peak and searching on both sides are all O(log n) operations.
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.
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 findInMountainArray(int target, struct MountainArray* mountainArr) {
11 int len = mountainArr->length(mountainArr);
12 int index = -1;
13 for (int i = 0; i < len; ++i) {
14 if (mountainArr->get(mountainArr, i) == target) {
15 return i;
16 }
17 }
18 return index;
19}The brute-force approach directly scans through the mountain array from the start to the finish, checking each element against the target. If an element equals the target, it returns the index. Otherwise, it returns -1. This basic method is straightforward but inefficient due to its time complexity.