/
Solution.java
executable file
·80 lines (66 loc) · 2.12 KB
/
Solution.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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class Solution {
public boolean search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while(l <= r){
int mid = l + (r-l)/2;
if(nums[mid] == target) return true;
if(nums[mid] <= nums[r]){
if(target > nums[mid] && target <= nums[r]) l = mid + 1;
else r--;
}
else{
if(target >= nums[l] && target < nums[mid]) r = mid - 1;
else l++;
}
}
return false;
}
}
public class Solution {
public boolean search(int[] A, int target) {
int s = 0;
int e = A.length;
while(s < e){
int mid = (s + e) /2;
if(A[mid] == target){
return true;
}
if(target < A[mid]){
// normal in first half
if (A[s] == A[mid]) {
if(A[mid] == A[e - 1]){
// special
s++;
e--;
}else{
s = mid + 1;
}
} else if(A[s] <= A[mid] && A[s] <= target){
e = mid;
// abnormal
}else if(A[mid] <= A[e - 1]){
e = mid;
}else {
s = mid + 1;
}
} else {
// normal in last half
if (A[mid] == A[e - 1]) {
if(A[s] == A[mid]){
s++;
e--;
}else{
e = mid;
}
} else if(A[mid] <= A[e - 1] && target <= A[e - 1]){
s = mid + 1;
} else if(A[s] <= A[mid]) {
s = mid + 1;
} else {
e = mid;
}
}
}
return false;
}
}