-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathLeetCode_00034.java
More file actions
90 lines (85 loc) · 2.86 KB
/
LeetCode_00034.java
File metadata and controls
90 lines (85 loc) · 2.86 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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package com.github.jerring.leetcode;
public class LeetCode_00034 {
// public int[] searchRange(int[] nums, int target) {
// // 找到数组中第一个大于或等于 target 的元素的下标
// int left = lowerBound(nums, target);
// // 如果数组中存在等于 target 的元素，则寻找数组中第一个大于 target 的元素的下标
// if (left < nums.length && nums[left] == target) {
// int right = upperBound(nums, target);
// return new int[] { left, right - 1 };
// }
// // 数组中不存在目标值，返回 [-1, -1]
// return new int[] { -1, -1 };
// }
//
// /**
// * 返回数组中第一个大于或等于 target 的元素的下标。
// * 若数组中元素均小于 target，则返回数组最后一个元素的下一个位置的下标。
// * @param nums 已排序数组
// * @param target 目标值
// * @return 第一个大于或等于 target 的元素的下标
// */
// private int lowerBound(int[] nums, int target) {
// int lo = 0;
// int hi = nums.length;
// while (lo < hi) {
// int mid = lo + (hi - lo) / 2;
// if (nums[mid] < target) {
// lo = mid + 1;
// } else {
// hi = mid;
// }
// }
// return lo;
// }
//
// /**
// * 返回数组中第一个大于 target 的元素的下标。
// * 若数组中元素均小于或等于 target，则返回数组最后一个元素的下一个位置的下标。
// * @param nums 已排序数组
// * @param target 目标值
// * @return 第一个大于 target 的元素的下标
// */
// private int upperBound(int[] nums, int target) {
// int lo = 0;
// int hi = nums.length;
// while (lo < hi) {
// int mid = lo + (hi - lo) / 2;
// if (nums[mid] <= target) {
// lo = mid + 1;
// } else {
// hi = mid;
// }
// }
// return lo;
// }
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) {
return new int[]{-1, -1};
}
int left = first(nums, target);
if (nums[left] != target) {
return new int[]{-1, -1};
}
int right = last(nums, target);
return new int[]{left, right};
}
private int first(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = l + r >>> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return r;
}
private int last(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = l + r + 1 >>> 1;
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
return r;
}
}