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
|
import static org.junit.Assert.assertSame;
import static org.junit.Assert.assertTrue;
public class SearchInRotatedSortedArrayII {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int pivot = getPivot(nums);
return binarySearch(0, pivot - 1, nums, target) || binarySearch(pivot, nums.length - 1, nums, target);
}
private int getPivot(int[] nums) {
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int middle = (start + end) / 2;
if (middle > 0 && nums[middle] < nums[middle - 1]) {
return middle;
}
if (nums[start] == nums[middle]) {
start++;
} else if (nums[start] > nums[middle]) {
end = middle;
} else {
start = middle;
}
}
return 0;
}
private boolean binarySearch(int start, int end, int[] nums, int target) {
while (start <= end) {
int middle = (start + end) / 2;
if (nums[middle] == target) {
return true;
}
if (nums[middle] < target) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return false;
}
@Test
public void test() {
int[] nums = new int[]{1, 1, 1, 1, 1, 1, 0};
assertSame(6, getPivot(nums));
nums = new int[]{1, 1, 1, 1, 1, 1, 1};
assertSame(0, getPivot(nums));
nums = new int[]{1, 2, 3, 1, 1, 1, 1};
assertSame(3, getPivot(nums));
assertTrue(search(nums, 3));
assertTrue(!search(nums, 4));
nums = new int[]{1};
assertTrue(!search(nums, 4));
assertTrue(search(nums, 1));
}
}
|