-
Notifications
You must be signed in to change notification settings - Fork 0
/
33.Search in Rotated Sorted Array.cpp
46 lines (43 loc) · 1.28 KB
/
33.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
class Solution {
public:
int bsearch(const std::vector<int> &nums, int beg, int end, int target) {
while (beg <= end) {
int mid = (beg + end) / 2;
if (nums[mid] == target)
return mid;
else if(nums[mid] < target)
beg = mid + 1;
else
end = mid - 1;
}
return -1;
}
int search(const std::vector<int> &nums, int beg, int end, int target) {
int idx1 = -1, idx2 = -1;
if (beg > end)
return -1;
int mid = (beg + end) / 2;
if (nums[mid] == target) {
return mid;
}
else if(mid == beg) {
idx1 = search(nums, beg + 1, end, target);
}
else if (nums[beg] < nums[mid]) {
idx1 = bsearch(nums, beg, mid, target);
idx2 = search(nums, mid + 1, end, target);
}
else if(nums[beg] > nums[mid]) {
idx1 = bsearch(nums, mid, end, target);
idx2 = search(nums, beg, mid - 1, target);
}
if (idx1 != -1)
return idx1;
if (idx2 != -1)
return idx2;
return -1;
}
int search(vector<int>& nums, int target) {
return search(nums, 0, nums.size() - 1, target);
}
};