aboutsummaryrefslogtreecommitdiff
path: root/find_mountain.c
blob: 91d11c1d942c1f05c54064d44bf2e330c9d7344c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// 1095. Find in Mountain Array
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>

/*
 * 1. find peak and record location and value that's already been queried, and
 * verify if target has happened
 * 2. if target has happened and idx <= peak, exit and return ans
 * 3. query right of mountain and return true if target is found
 * 4. query left of mountain and return true if target is found
 * 5. if target is not found, return -1
 */

int get(MountainArray *, int index);
int length(MountainArray *);

int find_peak(MountainArray *mountain_arr, int len, int *data, bool *flag,
              int target, int *idx) {
  int left = 0, right = len - 1, mid, l, m, r;
  while (left < right) {
    mid = (left + right) / 2;
    m = get(mountain_arr, mid);
    flag[mid] = true;
    data[mid] = m;
    if (m == target)
      *idx = fmin(*idx, mid);
    r = get(mountain_arr, mid + 1);
    flag[mid + 1] = true;
    data[mid + 1] = r;
    if (r == target)
      *idx = fmin(*idx, mid + 1);
    if (m < r)
      left = mid + 1;
    else {
      l = get(mountain_arr, mid - 1);
      flag[mid - 1] = true;
      data[mid - 1] = l;
      if (l == target)
        *idx = fmin(*idx, mid - 1);
      if (m > l)
        return mid;
      else
        right = mid - 1;
    }
  }
  return left;
}

int find_val(MountainArray *mountain_arr, int begin, int end, int val,
             int *data, bool *flag, bool up) {
  int left = begin, right = end, tmp;
  while (left < right) {
    int mid = left + (right - left) / 2;
    if (flag[mid])
      tmp = data[mid];
    else
      tmp = get(mountain_arr, mid);
    if (tmp == val)
      return mid;
    if (tmp > val) {
      if (up)
        right = mid - 1;
      else
        left = mid + 1;
    }
  }
  if (get(mountain_arr, left) == val)
    return left;
  else
    return -1;
}

int findInMountainArray(int target, MountainArray *mountain_arr) {
  int len = length(mountain_arr), *idx = malloc(sizeof(int)), ans;
  int *data = malloc(len * sizeof(int));
  bool *flag = calloc(len, sizeof(bool));
  *idx = INT_MAX;
  int peak = find_peak(mountain_arr, len, data, flag, target, idx);
  if (*idx <= peak) {
    ans = *idx;
    goto exit;
  }
  ans = find_val(mountain_arr, 0, peak, target, data, flag, true);
  if (ans == -1)
    ans = find_val(mountain_arr, peak + 1, len - 1, target, data, flag, false);
exit:
  free(data), free(flag);
  return ans;
}