-
Notifications
You must be signed in to change notification settings - Fork 28
/
Search_in_Rotated_Sorted_Array.cpp
59 lines (51 loc) · 1.83 KB
/
Search_in_Rotated_Sorted_Array.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
class Solution {
public:
int search(int start, int end, int target, vector<int>& A) {
if (start > end) return -1;
int mid = start + (end - start) / 2;
if (A[mid] == target) return mid;
if (A[mid] >= A[start]) {
if (target < A[mid] and target >= A[start]) {
return search(start, mid - 1, target, A);
} else {
return search(mid + 1, end, target, A);
}
}
if (A[mid] < A[start]) {
if (target < A[mid] or target >= A[start]) {
return search(start, mid - 1, target, A);
} else {
return search(mid + 1, end, target, A);
}
}
return -1;
}
int search(vector<int>& A, int target) {
// O(logn) Two pass needed (1) find pivot (2) search target
/*
int pivotIndx, mid, start = 0, end = n - 1;
while(A[start] > A[end]) {
mid = start + (end - start) / 2;
if(A[mid] >= A[start]) start = mid + 1;
else end = mid;
}
pivotIndx = start;
if(pivotIndx > 0 and target >= A[0] and target <= A[pivotIndx - 1])
start = 0, end = pivotIndx - 1;
else if(target >= A[pivotIndx] and target <= A[n - 1])
start = pivotIndx, end = n - 1;
else return -1;
while(start <= end) {
int mid = start + (end - start) / 2;
if(target < A[mid]) end = mid - 1;
else if (target > A[mid]) start = mid + 1;
else return mid;
}
return -1;
*/
// O(logn) one pass needed
int n = (int)A.size();
if(n == 0) return -1;
return search(0, n - 1, target, A);
}
};