leetcode

0 class Solution {

1 int find_peak(MountainArray &mountainArr) {

2 int left = 1, right = mountainArr.length() - 2;

3 while (left != right) {

4 const int mid = left + (right - left) / 2;

5 if (mountainArr.get(mid) < mountainArr.get(mid + 1))

6 left = mid + 1;

7 else

8 right = mid;

9 }

10 return left;

11 }

12

13 int find_left(MountainArray &mountainArr, int left, int right, int target) {

14 while (left != right) {

15 const int mid = left + (right - left) / 2;

16 if (mountainArr.get(mid) < target)

17 left = mid + 1;

18 else

19 right = mid;

20 }

21 return left;

22 }

23

24 int find_right(MountainArray &mountainArr, int left, int right, int target) {

25 while (left != right) {

26 const int mid = left + (right - left) / 2;

27 if (mountainArr.get(mid) > target)

28 left = mid + 1;

29 else

30 right = mid;

31 }

32 return left;

33 }

34

35 public:

36 int findInMountainArray(int target, MountainArray &mountainArr) {

37 const int peak = find_peak(mountainArr);

38

39 const int left = find_left(mountainArr, 0, peak, target);

40 if (mountainArr.get(left) == target) return left;

41

42 const int right = find_right(mountainArr, peak + 1, mountainArr.length() - 1, target);

43 if (mountainArr.get(right) == target) return right;

44

45 return -1;

46 }

47 };