-
Notifications
You must be signed in to change notification settings - Fork 0
/
searchin_rotatedsortedarr.cpp
54 lines (46 loc) · 1.05 KB
/
searchin_rotatedsortedarr.cpp
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
#include <iostream>
using namespace std;
int getPivot(int arr[], int n){
int s = 0;
int e = n - 1;
int mid = s + (e-s)/2;
while(s<e){
if(arr[mid] >= arr[0]){
s = mid + 1;
}
else{
e = mid;
}
mid = s + (e-s)/2;
}
return s;
}
int binarySearch(int arr[], int st,int end, int key){
int s = st;
int e = end;
int mid = s + (e-s)/2;
while(s<=e){
if(arr[mid] == key)
return mid;
if(arr[mid] > key)
s = mid + 1;
else
e = mid - 1;
mid = s + (e-s)/2;
}
return -1;
}
int findPosition(int arr[], int n, int k){
int pivot = getPivot(arr, n);
if(k >= arr[pivot] && k <= arr[n-1]){
return binarySearch(arr, pivot, n-1, k);
}
else{
return binarySearch(arr, 0, pivot - 1, k);
}
}
int main(){
int arr[5] = {7,8,1,2,3};
int k = 2;
cout<<"Position of: "<<k<<" is: "<<findPosition(arr, 5, k);
}