aboutsummaryrefslogtreecommitdiff
path: root/find_mountain.c
diff options
context:
space:
mode:
Diffstat (limited to 'find_mountain.c')
-rw-r--r--find_mountain.c91
1 files changed, 91 insertions, 0 deletions
diff --git a/find_mountain.c b/find_mountain.c
new file mode 100644
index 0000000..91d11c1
--- /dev/null
+++ b/find_mountain.c
@@ -0,0 +1,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;
+}