-
Notifications
You must be signed in to change notification settings - Fork 0
/
Search in rotated array
49 lines (47 loc) · 1.06 KB
/
Search in rotated array
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
class Solution {
public:
int search(vector<int>& arr, int target) {
int l = 0 ;
int r = arr.size() - 1;
if(arr.size() == 1)
{
if(arr[0] == target)
{
return 0 ;
}
return -1 ;
}
while( l <= r)
{
int mid = (l + r) / 2;
if(arr[mid] == target)
{
return mid ;
}
//is left sorted
if(arr[mid] > arr[l])
{
if(target >= arr[l] && target <= arr[mid - 1])
{
r = mid - 1 ;
}
else
{
l = mid + 1 ;
}
}
else
{
if(target >= arr[mid + 1] && target <= arr[r])
{
l= mid + 1 ;
}
else
{
r = mid - 1 ;
}
}
}
return -1;
}
};