forked from algorithm024/algorithm024
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSearch_33.java
More file actions
64 lines (62 loc) · 2.04 KB
/
Copy pathSearch_33.java
File metadata and controls
64 lines (62 loc) · 2.04 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class Search_33 {
/**
* 采用二分法求解：
* 这样写放到leetcode上执行提示超出时间限制，同样用的二分查找算法，只是归约边界判定条件写的繁琐，复杂度应该还是O(logN)
* @param nums
* @param target
* @return
*/
// public static int search(int[] nums, int target) {
// int begin = 0;
// int end = nums.length - 1;
// int mid = (end + begin) / 2;
// while(end - begin > 0) {
// if(nums[mid] < nums[begin]) {
// if(target < nums[mid]) {
// end = mid;
// }else if(target > nums[end]) {
// end = mid;
// }else {
// begin = mid;
// }
// }else {
// if(target > nums[mid]) {
// begin = mid;
// }else if(target < nums[begin]) {
// begin = mid;
// }else {
// end = mid;
// }
// }
// mid = (end + begin) / 2;
// }
// return nums[begin] == target ? begin : -1;
// }
/**
* 二分法求解：简化规约边界判定条件
* @param nums
* @param target
* @return
*/
public static int search(int[] nums, int target) {
int begin = 0;
int end = nums.length - 1;
while (begin < end) {
int mid = (begin + end) / 2;
// 当[0,mid]有序时,向后规约条件
if (nums[0] <= nums[mid] && (target > nums[mid] || target < nums[0])) {
begin = mid + 1;
// 当[0,mid]发生旋转时,向后规约条件
} else if (target > nums[mid] && target < nums[0]) {
begin = mid + 1;
} else {
end = mid;
}
}
return nums[begin] == target ? begin : -1;
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
System.out.println(search(nums, 0));
}
}