DSA/Search_in_Bitonic_Array.cpp at main · riteshkantule/DSA · 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
57
58
59
60
61
62
63
int binarySearch(vector<int> &A, int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;

        if (A[mid] == x)
            return mid;

        if (A[mid] > x)
            return binarySearch(A, l, mid - 1, x);

        return binarySearch(A, mid + 1, r, x);
    }

    return -1;
}

int binarySearch2(vector<int> &A, int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;

        if (A[mid] == x)
            return mid;

        if (A[mid] > x)
            return binarySearch2(A, mid + 1, r, x);

        return binarySearch2(A, l, mid - 1, x);
    }

    return -1;
}

int bitonic_Search(vector<int> &A, int l, int r) {
    if (r >= l) {
        int mid = l + (r - l) / 2;

        if (A[mid] > A[mid + 1] && A[mid] < A[mid - 1])
            return mid;

        if (A[mid] > A[mid + 1])
            return bitonic_Search(A, l, mid - 1);

        return bitonic_Search(A, mid + 1, r);
    }

    return -1;
}

int Solution::solve(vector<int> &A, int B) {
    int N = A.size();
    int r = N - 1;
    int l = 0;

    int Mid_of_Bitonic = bitonic_Search(A, 0, N - 1);

    int result1 = binarySearch(A, 0, Mid_of_Bitonic, B);
    int result2 = binarySearch2(A, Mid_of_Bitonic, N - 1, B);

    if (result1 == -1 && result2 == -1)
        return -1;
    else
        return result1 + result2 + 1;
}