Array/Search in a Rotated Array at master · shalikpatel/Array · 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
64
65
66

/*
Given a sorted and rotated array A of N distinct elements which is rotated at some point,
and given an element K. The task is to find the index of the given element K in the array A.

*/

#include <iostream>
using namespace std;

int binary_search(long long int arr[], int l, int r, long long int k)
{
    if(l > r) {
        return -1;
    }
    int mid = (l + r) / 2;
    if(arr[mid] == k) {
        return mid;
    } else if(k > arr[mid]) {
        return binary_search(arr, mid+1, r, k);
    } else {
        return binary_search(arr, l, mid-1, k);
    }
}

int search(long long int arr[], int l, int r)
{
    if(arr[l] < arr[r]) {
        return l;
    }
    int mid = (l + r) / 2;
    if(arr[mid] > arr[mid+1]) {
        return mid+1;
    }
    if(arr[l] < arr[mid]) {
        return search(arr, mid + 1, r);
    } else {
        return search(arr, l, mid-1);
    }

}

int main() {
    int n;
    cin >> n;
    long long int arr[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    long long int k;
    cin >> k;

    int pivot = search(arr, 0, n-1);
    // cout << pivot << endl;
    if(pivot == 0) {
        cout << binary_search(arr, 0, n-1, k) << endl;
    } else {
        if(k >= arr[0] && k <= arr[pivot-1]) {
            cout << binary_search(arr, 0, pivot-1, k) << endl;
        } else {
            cout << binary_search(arr, pivot, n-1, k) << endl;
        }
    }

	return 0;
}