-
Notifications
You must be signed in to change notification settings - Fork 71
/
Question02SearchForARange.java
70 lines (65 loc) · 1.9 KB
/
Question02SearchForARange.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
package ninechapter.ch02_binary_search_and_sorted_array;
/**
* Created by anduo on 17-3-12.
* http://www.lintcode.com/zh-cn/problem/search-for-a-range/
* https://leetcode.com/problems/search-for-a-range
* <h1>描述</h1>
* <p>
* 给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。<br/>
* 如果目标值不在数组中,则返回[-1, -1]
* </p>
* 给出[5, 7, 7, 8, 8, 10]和目标值target=8,
* 返回[3, 4]
*/
public class Question02SearchForARange {
public int[] searchRange(int[] A, int target) {
if (A == null || A.length == 0) {
return new int[]{-1, -1};
}
int[] bound = new int[2];
int start, end, mid;
// search for left bound
start = 0;
end = A.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] == target) {
end = mid;
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[start] == target) {
bound[0] = start;
} else if (A[end] == target) {
bound[0] = end;
} else {// miss value
bound[0] = bound[1] = -1;
return bound;
}
// search for right bound
start = 0;
end = A.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] == target) {
start = mid;
} else if (A[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (A[end] == target) {
bound[1] = end;
} else if (A[start] == target) {
bound[1] = start;
} else {
bound[0] = bound[1] = -1;
return bound;
}
return bound;
}
}