-
Notifications
You must be signed in to change notification settings - Fork 0
/
SearchForARange.java
65 lines (64 loc) · 1.84 KB
/
SearchForARange.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
public class Solution {
public int[] searchRange(int[] a, int target) {
int start = 0, end = a.length - 1;
int rstart = -1, rend = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (a[mid] == target) {
if (mid == start) {
rstart = start;
break;
}
end = mid;
}
else if (a[mid] < target)
start = mid + 1;
else
end = mid -1;
}
start = 0;
end = a.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (a[mid] <= target) {
start = mid + 1;
}
else {
end = mid - 1;
}
}
if (rstart >= 0)
return new int[] {rstart, start - 1};
else
return new int[] { -1, -1 };
}
public int[] searchRange2(int[] a, int target) {
int x = -1, y = -1;
int start = 0, end = a.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target == a[mid]) {
x = (x == -1) ? mid : Math.min(x, mid);
start = mid + 1;
}
else if (target > a[mid])
start = mid + 1;
else
end = mid - 1;
}
start = 0;
end = a.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (target == a[mid]) {
y = (y == -1) ? mid : Math.max(y, mid);
end = mid - 1;
}
else if (target > a[mid])
start = mid + 1;
else
end = mid - 1;
}
return new int[] { x, y };
}
}