問題
小さいnums と、target をnums のtarget の[最初, 最後] の
numsは小さい 順に 並んでいます。 同じ 値が 続く こともあります targetがnumsに無い ときは [-1, -1]を返します。 numsが空の ときも同じです numsの長さは 0 以上 100000 以下、 値と targetはどれも -1000000000 以上 1000000000 以下です - 前から 1 つずつ
見る 書き方ではなく、 並びの 長さを n として O(log n) の 手間で 解いてください
入力と出力の例
例 1
4 は 1 番目から 3 番目まで
入力
nums = [2, 4, 4, 4, 7, 9]
target = 4出力
[1, 3]例 2
6 は
入力
nums = [1, 3, 5, 8]
target = 6出力
[-1, -1]例 3
並びが
入力
nums = [6, 6, 6]
target = 6出力
[0, 2]面接での聞かれ方
面接では、
- 「並んだ数の
中で、 ある 値が 出てくる 範囲を 返してください。 O(log n) で お願いします」 - 最初に
前から 数える 書き方を 答えると、 「同じ 値が 10 万個続いたら どうなりますか？」と 聞き返されます - 書き終えた
あとに 「その 値が いくつあるかも O(log n) で 数えられますか？」と 続けて 聞かれる ことがあります
二分探索は、
アルゴリズムのチートシートの「ソートと二分探索」に、この型の要点を表とコードでまとめています。
まず
段 1
まずtarget を 1 つ
段 2
そこで、target 以上のtarget よりtarget 以上、というx より
段 3
最後のtarget + 1 以上のtarget のtarget よりtarget + 1 以上です。
段 4
端のtarget よりtarget はtarget でなければ、target より[-1, -1] を
解答
Python
Python
def target_range(nums, target):
def lower(x):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
first = lower(target)
if first == len(nums):
return [-1, -1]
if nums[first] != target:
return [-1, -1]
last = lower(target + 1) - 1
return [first, last]JavaScript
JavaScript
function targetRange(
nums, target
) {
const lower = (x) => {
let lo = 0;
let hi = nums.length;
while (lo < hi) {
const m = (lo + hi) >> 1;
if (nums[m] < x) {
lo = m + 1;
} else {
hi = m;
}
}
return lo;
};
const first = lower(target);
if (first === nums.length) {
return [-1, -1];
}
if (nums[first] !== target) {
return [-1, -1];
}
const last =
lower(target + 1) - 1;
return [first, last];
}Go
Go
func targetRange(
nums []int, target int,
) []int {
lower := func(x int) int {
lo, hi := 0, len(nums)
for lo < hi {
mid := (lo + hi) / 2
if nums[mid] < x {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
first := lower(target)
if first == len(nums) {
return []int{-1, -1}
}
if nums[first] != target {
return []int{-1, -1}
}
last := lower(target+1) - 1
return []int{first, last}
}lower の hi は、x より
計算量
- 時間は O(log n) です。
lowerは 1 回ごとに範囲を 半分にし、 それを 2 回呼ぶだけです - 使う
記憶は O(1) です。 lo、hi、midなどの決まった 数の 置き場だけを使います
よく
- 見つけてから
左右へ広げる。 同じ 値が 長く 続くと、 広げる 所が O(n) に なります。 両端を それぞれ二分探索で求めます hiを最後の 位置から始める。 hi = len(nums) - 1から始めると、 全部が targetより小さい 場合と、 最後の 1 つだけが targetの場合を 見分けられず、 範囲を 1 つ 取り こぼします - 止める
条件と 狭め方が 合っていない。 while lo < hiのままhi = mid - 1と書くと、 切れ目の 位置を 飛び越えます。 逆に lo = midと書くと、 loとhiが隣どうしの ときに midが動かず止まらなくなります - 見つからない
場合を 確かめない。 lower(target)の位置を 確かめずに 返すと、 targetが無いのに 隣の 値の 位置を 答えてしまいます。 位置が 長さと 同じか、 その 値が targetかを必ず見ます
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「見つけてから
左右へ 広げると、 同じ 値が 続いた ときに O(n) に なります。 そこで、 ある 値以上が 始まる 位置を 返す二分探索を 1 つ 作り、 targetとtarget + 1で 2 回呼びます。1 回目が 最初の 位置、 2 回目の 1 つ 手前が 最後の 位置です。 1 回目の 位置に targetが無ければ [-1, -1]です。時間は O(log n)、 記憶は O(1) です。」
書き終えたら、
「例 1 で
たどります。 4 以上が 始まる 位置を 探すと、 0 番の 2 は 小さいので 外れ、 1 番の 4 で 止まります。 5 以上が 始まる 位置は 4 番の 7 なので、 その 1 つ手前の 3 番が 最後です。 答えは [1, 3]です。」