-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSearch in Rotated Sorted Array 08-07-24 POTD.cpp
67 lines (65 loc) · 1.6 KB
/
Search in Rotated Sorted Array 08-07-24 POTD.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
55
56
57
58
59
60
61
62
63
64
65
66
67
// https://www.geeksforgeeks.org/problems/search-in-a-rotated-array4618/1
class Solution {
public:
int findKey(vector<int> arr, int i, int j, int key){
while(i<=j){
if(arr[i]==key){
return i;
}
else if(arr[j] == key){
return j;
}
int mid = (i+j)/2;
if(arr[mid]==key){
return mid;
}
else if(arr[mid] > key){
j = mid-1;
}
else{
i = mid+1;
}
}
return -1;
}
int search(vector<int>& arr, int key) {
// complete the function here
int n = arr.size();
int ans = -1;
int l = 0, r = n-1, point = 0;
if(arr[0]==key){
return 0;
}
if(arr[n-1]==key){
return n-1;
}
if(arr[l] < arr[r]){
return findKey(arr, 0, n-1, key);
}
while(l < r){
int mid = (l+r)/2;
if(mid>0 && arr[mid]<arr[mid-1]){
point = mid;
break;
}
else if(mid<n && arr[mid]>arr[mid+1]){
point = mid+1;
break;
}
else{
if(arr[mid+1] < arr[l]){
r = mid-1;
}
else
l = mid+1;
}
}
if(arr[n-1] > key){
ans = findKey(arr, point, n-1, key);
}
else{
ans = findKey(arr, 0, point-1, key);
}
return ans;
}
};