1+ /* *
2+ * Description:
3+ * (This problem is an interactive problem.)
4+ *
5+ * You may recall that an array arr is a mountain array if and only if:
6+ * arr.length >= 3
7+ * There exists some i with 0 < i < arr.length - 1 such that:
8+ * arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
9+ * arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
10+ *
11+ * Given a mountain array mountainArr, return the minimum index such that
12+ * mountainArr.get(index) == target. If such an index does not exist, return -1.
13+ *
14+ * You cannot access the mountain array directly. You may only access the array using
15+ * a MountainArray interface:
16+ * MountainArray.get(k) returns the element of the array at index k (0-indexed).
17+ * MountainArray.length() returns the length of the array.
18+ *
19+ * Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer.
20+ * Also, any solutions that attempt to circumvent the judge will result in disqualification.
21+ *
22+ * Ex1.
23+ * Input: array = [1,2,3,4,5,3,1], target = 3
24+ * Output: 2
25+ * Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index,
26+ * which is 2.
27+ *
28+ * Ex2.
29+ * Input: array = [0,1,2,4,2,1], target = 3
30+ * Output: -1
31+ * Explanation: 3 does not exist in the array, so we return -1.
32+ *
33+ * Algorithm:
34+ * 1. The algorithm's goal is to find the minimum index at which the value "target",
35+ * exist within a "MountainArray".
36+ * 2. It employs a binary search approach, dividing the array into ascending and
37+ * descending halves.Additionally, it identifies the peak index to determine the
38+ * transition from ascending to descending.
39+ *
40+ * Time Complexity: O(log n)
41+ * Space Complexity: O(1)
42+ */
43+
44+ /* *
45+ * // This is the MountainArray's API interface.
46+ * // You should not implement it, or speculate about its implementation
47+ * class MountainArray {
48+ * public:
49+ * int get(int index);
50+ * int length();
51+ * };
52+ */
53+
54+ class Solution {
55+ public:
56+ int binarySearch (int & begin,int & end,const int & target, MountainArray &mountainArr)
57+ {
58+ while (begin <= end)
59+ {
60+ int mid = begin + (end-begin)/2 ;
61+ int mid_number = mountainArr.get (mid);
62+
63+ if (mid_number == target)
64+ {
65+ return mid;
66+ }
67+ else if (mid_number > target)
68+ {
69+ end = --mid;
70+ }
71+ else
72+ {
73+ begin = ++mid;
74+ }
75+ }
76+ return -1 ;
77+ }
78+
79+ int reverseBinarySearch (int & begin,int & end,const int & target, MountainArray &mountainArr)
80+ {
81+ while (begin <= end)
82+ {
83+ int mid = begin + (end-begin)/2 ;
84+ int mid_number = mountainArr.get (mid);
85+
86+ if (mid_number == target)
87+ {
88+ return mid;
89+ }
90+ else if (mid_number > target)
91+ {
92+ begin = ++mid;
93+ }
94+ else
95+ {
96+ end = --mid;
97+ }
98+ }
99+ return -1 ;
100+ }
101+
102+ int findPeakElement (int & begin,int & end, MountainArray &mountainArr)
103+ {
104+ while (begin < end)
105+ {
106+ int mid = begin + (end-begin)/2 ;
107+ if (mountainArr.get (mid) < mountainArr.get (mid+1 ))
108+ {
109+ begin = ++mid;
110+ }
111+ else
112+ {
113+ end = --mid;
114+ }
115+ }
116+ return begin;
117+ }
118+
119+ int findInMountainArray (int target, MountainArray &mountainArr) {
120+ ios_base::sync_with_stdio (false );
121+ cin.tie (NULL );
122+
123+ int begin =0 ;
124+ int end = mountainArr.length ()-1 ;
125+ int minimum_index =0 ;
126+
127+ int peak_index =findPeakElement (begin, end, mountainArr);
128+
129+ begin =0 ;
130+ end = peak_index;
131+ minimum_index =binarySearch (begin, end, target, mountainArr);
132+
133+ if (minimum_index != -1 )return minimum_index;
134+
135+ begin = peak_index;
136+ end = mountainArr.length ()-1 ;
137+ minimum_index =reverseBinarySearch (begin, end, target, mountainArr);
138+
139+ return minimum_index;
140+ }
141+ };