1+ /* *
2+ *
3+ * Algorithm:
4+ * - The algorithm's goal is to find the minimum index at which the value "target",
5+ * exist within a "MountainArray".
6+ * - It employs a binary search approach, dividing the array into ascending and
7+ * descending halves. Additionally, it identifies the peak index to determine the
8+ * transition from ascending to descending.
9+ *
10+ * Time Complexity: O(log n)
11+ * Space Complexity: O(1)
12+ *
13+ */
14+
15+ /* *
16+ * // This is the MountainArray's API interface.
17+ * // You should not implement it, or speculate about its implementation
18+ * class MountainArray {
19+ * public:
20+ * int get(int index);
21+ * int length();
22+ * };
23+ */
24+
25+ class Solution {
26+ public:
27+ int binarySearch (int & begin,int & end,const int & target, MountainArray &mountainArr)
28+ {
29+ while (begin <= end)
30+ {
31+ int mid = begin + (end-begin)/2 ;
32+ int mid_number = mountainArr.get (mid);
33+
34+ if (mid_number == target)
35+ {
36+ return mid;
37+ }
38+ else if (mid_number > target)
39+ {
40+ end = --mid;
41+ }
42+ else
43+ {
44+ begin = ++mid;
45+ }
46+ }
47+ return -1 ;
48+ }
49+
50+ int reverseBinarySearch (int & begin,int & end,const int & target, MountainArray &mountainArr)
51+ {
52+ while (begin <= end)
53+ {
54+ int mid = begin + (end-begin)/2 ;
55+ int mid_number = mountainArr.get (mid);
56+
57+ if (mid_number == target)
58+ {
59+ return mid;
60+ }
61+ else if (mid_number > target)
62+ {
63+ begin = ++mid;
64+ }
65+ else
66+ {
67+ end = --mid;
68+ }
69+ }
70+ return -1 ;
71+ }
72+
73+ int findPeakElement (int & begin,int & end, MountainArray &mountainArr)
74+ {
75+ while (begin < end)
76+ {
77+ int mid = begin + (end-begin)/2 ;
78+ if (mountainArr.get (mid) < mountainArr.get (mid+1 ))
79+ {
80+ begin = ++mid;
81+ }
82+ else
83+ {
84+ end = --mid;
85+ }
86+ }
87+ return begin;
88+ }
89+
90+ int findInMountainArray (int target, MountainArray &mountainArr) {
91+ ios_base::sync_with_stdio (false );
92+ cin.tie (NULL );
93+
94+ int begin =0 ;
95+ int end = mountainArr.length ()-1 ;
96+ int minimum_index =0 ;
97+
98+ int peak_index =findPeakElement (begin, end, mountainArr);
99+
100+ begin =0 ;
101+ end = peak_index;
102+ minimum_index =binarySearch (begin, end, target, mountainArr);
103+
104+ if (minimum_index != -1 )return minimum_index;
105+
106+ begin = peak_index;
107+ end = mountainArr.length ()-1 ;
108+ minimum_index =reverseBinarySearch (begin, end, target, mountainArr);
109+
110+ return minimum_index;
111+ }
112+ };