Find in Mountain Array LeetCode solution in C++

1
/**
2
 * // This is the MountainArray's API interface.
3
 * // You should not implement it, or speculate about its implementation
4
 * class MountainArray {
5
 * public:
6
 * int get(int index);
7
 * int length();
8
 * };
9
 */
10

11
class Solution {
12
 public:
13
  //----------------------- find peak ---------------------------------------
14

15
  int find_max(MountainArray &mountainArr, int start, int end) {
16
    int n = mountainArr.length();
17
    while (start <= end) {
18
      int mid = start + (end - start) / 2;
19
      int next = (mid + 1) % n;
20
      int prev = (mid + n - 1) % n;
21

22
      int mid_val = mountainArr.get(mid);
23
      int pre_val = mountainArr.get(prev);
24
      int next_val = mountainArr.get(next);
25

26
      if (mid_val > next_val and mid_val > pre_val)
27
        return mid;
28

29
      else if (mid_val < next_val and mid_val > pre_val)
30
        start = mid + 1;
31

32
      else if (mid_val > next_val and mid_val < pre_val)
33
        end = mid - 1;
34
    }
35
    return -1;
36
  }
37

38
  //--------------------------binary
39
  // search-------------------------------------------
40

41
  int binary_search(MountainArray &mountainArr, int start, int end, int target) {
42
    while (start <= end) {
43
      int mid = start + (end - start) / 2;
44
      int mid_val = mountainArr.get(mid);
45

46
      if (mid_val == target)
47
        return mid;
48
      else if (target < mid_val) {
49
        end = mid - 1;
50
      } else
51
        start = mid + 1;
52
    }
53
    return -1;
54
  }
55

56
  //----------------------binary search in reverse
57
  // sorted------------------------------
58

59
  int binary_search_rev(MountainArray &mountainArr, int start, int end, int target) {
60
    while (start <= end) {
61
      int mid = start + (end - start) / 2;
62
      int mid_val = mountainArr.get(mid);
63
      if (mid_val == target)
64
        return mid;
65
      else if (target > mid_val) {
66
        end = mid - 1;
67
      } else
68
        start = mid + 1;
69
    }
70
    return -1;
71
  }
72

73
  //------------------------------returns minimum index of
74
  // target--------------------------------------
75

76
  int evaluate_ans(int a, int b) {
77
    if (a == -1 and b == -1)
78
      return -1;
79
    else if (a != -1 and b != -1)
80
      return min(a, b);
81
    else if (a == -1 and b != -1)
82
      return b;
83
    else
84
      return a;
85
  }
86

87
  int findInMountainArray(int target, MountainArray &mountainArr) {
88
    int start = 0;
89
    int n = mountainArr.length() - 1;
90
    int max_in = find_max(mountainArr, start, n);
91

92
    int a = binary_search(mountainArr, start, max_in, target);
93
    int b = binary_search_rev(mountainArr, max_in + 1, n, target);
94

95
    return evaluate_ans(a, b);
96
  }
97
};