34 Search for a Range

1. Question

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(logn).
If the target is not found in the array, return[-1, -1].
For example, Given[5, 7, 7, 8, 8, 10]and target value 8, return[3, 4].

2. Implementation

(1) Binary Search
1
class Solution {
2
public int[] searchRange(int[] nums, int target) {
3
int[] res = {-1, -1};
4
5
if (nums == null || nums.length == 0) {
6
return res;
7
}
8
9
int start = 0, end = nums.length - 1, mid = 0;
10
11
while (start + 1 < end) {
12
mid = start + (end - start) / 2;
13
14
if (nums[mid] < target) {
15
start = mid + 1;
16
}
17
else {
18
end = mid;
19
}
20
}
21
22
if (nums[start] == target) {
23
res[0] = start;
24
}
25
else if (nums[end] == target) {
26
res[0] = end;
27
}
28
else {
29
return res;
30
}
31
32
end = nums.length - 1;
33
34
while (start + 1 < end) {
35
mid = start + (end - start) / 2;
36
37
if (nums[mid] > target) {
38
end = mid - 1;
39
}
40
else {
41
start = mid;
42
}
43
}
44
45
if (nums[end] == target) {
46
res[1] = end;
47
}
48
else if (nums[start] == target) {
49
res[1] = start;
50
}
51
else {
52
return res;
53
}
54
return res;
55
}
56
}
Copied!

3. Time & Space Complexity

Binary Search: 时间复杂度O(logn), 空间复杂度O(1)