1+ /**
2+ * // This is MountainArray's API interface.
3+ * // You should not implement it, or speculate about its implementation
4+ * interface MountainArray {
5+ * public int get(int index) {}
6+ * public int length() {}
7+ * }
8+ */
9+
10+ class Solution {
11+ public int findInMountainArray (int target ,MountainArray mountainArr ) {
12+ int maxIndex =findMax (mountainArr );
13+ int leftResult =binarySearchLeft (mountainArr ,target ,maxIndex );
14+ int rightResult =binarySearchRight (mountainArr ,target ,maxIndex );
15+
16+ return (leftResult == -1 &&rightResult == -1 ) ? -1 :leftResult == -1 ?rightResult :leftResult ;
17+ }
18+
19+ public int findMax (MountainArray array ) {
20+ int left =0 ;
21+ int right =array .length () -1 ;
22+
23+ while (left <=right ) {
24+ int mid =left + (right -left )/2 ;
25+ if (array .get (mid ) <array .get (mid +1 )) {
26+ left =mid +1 ;
27+ }else {
28+ right =mid -1 ;
29+ }
30+ }
31+
32+ return left ;
33+ }
34+
35+ public int binarySearchLeft (MountainArray array ,int target ,int right ) {
36+ int left =0 ;
37+
38+ while (left <=right ) {
39+ int mid =left + (right -left )/2 ;
40+ int midValue =array .get (mid );
41+ if (midValue <target ) {
42+ left =mid +1 ;
43+ }else if (midValue >target ) {
44+ right =mid -1 ;
45+ }else {
46+ return mid ;
47+ }
48+ }
49+ return -1 ;
50+ }
51+
52+ public int binarySearchRight (MountainArray array ,int target ,int left ) {
53+ int right =array .length () -1 ;
54+
55+ while (left <=right ) {
56+ int mid =left + (right -left )/2 ;
57+ int midValue =array .get (mid );
58+
59+ if (midValue <target ) {
60+ right =mid -1 ;
61+ }else if (midValue >target ) {
62+ left =mid +1 ;
63+ }else {
64+ return mid ;
65+ }
66+ }
67+ return -1 ;
68+ }
69+ }