-
Notifications
You must be signed in to change notification settings - Fork 0
/
SearchInRotatedSortedArray.java
52 lines (50 loc) · 1.92 KB
/
SearchInRotatedSortedArray.java
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
import java.util.Arrays;
/*
* https://leetcode.com/problems/search-in-rotated-sorted-array/
*/
public class SearchInRotatedSortedArray {
public int search(int[] nums, int target) {
System.out.println(Arrays.toString(nums));
if (nums.length == 0) {
return -1;
}
int midIndex = nums.length >> 1;
int mid = nums[midIndex];
if (mid == target) {
return midIndex;
}
if (mid > target) {
if (nums[0] == target) {
return 0;
} else if (nums[0] > target) {
if (mid > nums[0]) {
int result = search(Arrays.copyOfRange(nums, midIndex + 1, nums.length), target);
return result == -1 ? result : result + midIndex + 1;
} else {
return search(Arrays.copyOfRange(nums, 0, midIndex), target);
}
} else {
int result = Arrays.binarySearch(nums, 0, midIndex, target);
return result >= 0 ? result : -1;
}
} else {
int lastIndex = nums.length - 1;
if (nums[lastIndex] == target) {
return lastIndex;
} else if (nums[lastIndex] > target) {
int result = Arrays.binarySearch(nums, midIndex, nums.length, target);
return result >= 0 ? result : -1;
} else {
if (mid > nums[lastIndex]) {
int result = search(Arrays.copyOfRange(nums, midIndex + 1, nums.length), target);
return result == -1 ? result : result + midIndex + 1;
} else {
return search(Arrays.copyOfRange(nums, 0, midIndex), target);
}
}
}
}
public static void main(String[] args) {
System.out.println(new SearchInRotatedSortedArray().search(new int[]{4,5,6,7,0,1,2}, 0)); // 4
}
}