-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSearch in Rotated Sorted Array
More file actions
43 lines (43 loc) · 1.32 KB
/
Search in Rotated Sorted Array
File metadata and controls
43 lines (43 loc) · 1.32 KB
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
public class Solution {
public int search(int[] A, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if(A.length == 0) return -1;
if(A.length == 1)
if(A[0] == target)
return 0;
else
return -1;
int start=1, end=0;
while(start<A.length && A[start]>A[end])
{
if(A[start] == target || A[end] == target)
return A[start] == target ? start : end;
start++;
end++;
}
if(start == A.length) //no rotation, search the entire array
{
return -1;
}
if(target>A[end] || target<A[start])
return -1;
else if(target == A[0])
return 0;
else if(target > A[0]) //has searched the integers between A[0] and A[end]
return -1;
else
return helpler(A, start, A.length-1, target);
}
private int helpler(int[] A, int low, int high, int target)
{
if(low>high)
return -1;
int mid = (low+high)/2;
if(A[mid] == target)
return mid;
else if(A[mid]>target)
return helpler(A, low, mid-1, target);
else
return helpler(A, mid+1, high, target);
}
}