LeetCode/1095-Find-in-Mountain-Array.java at main · iamAmer/LeetCode · GitHub

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
class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int peak = peakIndexInMountainArray(mountainArr);
        int result = orderAgnosticBs(mountainArr, target, 0, peak);
        if(result != -1) {
            return result;
        } else {
            return orderAgnosticBs(mountainArr, target, peak+1, mountainArr.length() -1);
        }
    }

    public int peakIndexInMountainArray(MountainArray mountainArr) {

        int start = 0;
        int end = mountainArr.length() - 1;

        while(start < end) {
            int mid = start + (end - start)/2;

            if(mountainArr.get(mid) > mountainArr.get(mid+1)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    public int orderAgnosticBs(MountainArray mountainArr, int target, int start, int end) {

        boolean isAsc = mountainArr.get(start) < mountainArr.get(end);

        while(start <= end) {
            int mid = start + (end-start)/2;

            if(target == mountainArr.get(mid)) {
                return mid;
            }

            if(isAsc) {
                if(target < mountainArr.get(mid)) {
                    end = mid - 1;
                } else if(target > mountainArr.get(mid)){
                    start = mid + 1;
                }
            } else {
                if(target < mountainArr.get(mid)) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}