配列はソート済みなので、二分探索を2回行って境界を求められる。1回目は値が target 以上となる最初のインデックスを探し、2回目は値が target より大きくなる最初のインデックスを探す。1回目の境界が配列の末尾、またはその位置の値が target でなければ、対象の値は存在しない。そうでなければ、1回目の境界と2回目の境界から1を引いたインデックスが答えとなる。target + 1 を計算せず、target より大きい値を直接探索するため、Integer.MAX_VALUE でもオーバーフローしない。
探索対象の境界が半開区間 [left, right) に残ることがループ不変条件である。各反復で残りのインデックスを少なくとも半分に絞るため、2回の探索の時間計算量は O(log N)。追加領域の計算量は O(1)。
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
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = lowerBound(nums, target);
if (left == nums.length || nums[left] != target) {
return new int[] {-1, -1};
}
int right = upperBound(nums, target);
return new int[] {left, right - 1};
}
private int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private int upperBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}