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)); } }
|