問題と適用される文脈
非減少順にソートされた整数配列 nums と整数 target が与えられたとき、target の最初と最後のインデックスを返します。 存在しない場合は [-1, -1] を返します。配列は空である可能性があり、重複を含むこともあります。また、関数は配列を 変更してはなりません。求められる計算量は O(log n) の時間計算量と O(1) の追加空間計算量です。
例えば、nums = [1, 2, 2, 2, 3] と target = 2 の場合は [1, 3] を返し、target = 4 の場合は [-1, -1] を返します。 線形探索でも答えを出すことはできますが、最悪計算量が O(n) となり要件を満たせません。
この問題は、ソフトウェアエンジニアリングやアルゴリズム職のコーディング面接に適しています。Amazon の現在の SDE II 面接ガイドでは、 構文的に正しく、スケーラブルで堅牢、かつ十分にテストされたコードが求められます。LeetCode でも同様のコア問題が提供されています。 真の試金石は、2 つのテンプレートを暗記しているかどうかではありません。ループ条件、区間の更新、戻り値のすべてが単一の不変条件に従うように、 探索境界をどれだけ正確に定義できるかです。
面接官が評価しているポイント
第 1 のシグナルは、候補者が「単にどれか 1 つの出現箇所を見つけるだけでは不十分である」と認識しているかどうかです。 一致した時点でリターンする通常の二分探索では、最も左側または最も右側の出現箇所である保証はありません。1 つ見つけてから 外側に向かって線形スキャンすると、すべての要素がターゲットと等しい場合に依然として O(n) に低下します。
第 2 のシグナルは、境界のセマンティクスです。明快なアプローチでは、2 つの挿入ポイントを探索します：
lowerBound: 値がtarget以上である最初の位置。upperBound: 値がtargetより厳密に大きい最初の位置。
Python の公式 bisect_left と bisect_right は、これらの分割定義を採用しています。両方のポイントが正しければ、 存在するターゲットは [lowerBound, upperBound - 1] の範囲を占めることになります。
第 3 のシグナルは、ループ不変条件です。半開区間 [left, right) を用いると、空配列は自然に [0, 0) として開始され、 終了条件は left === right となります。閉区間のルールと半開区間の初期化を混同し、right を nums.length に設定した後に nums[right] を読み取ったりすると、範囲外アクセスや無限ループの原因になります。
最後に、面接官は検証能力を確認します。優れた回答では、空配列、1 要素、全重複、ターゲットが最小値未満、 ターゲットが最大値超過、両端に存在するターゲット、存在しないターゲットなどのケースを網羅します。また、target + 1 が 汎用的な上限テクニックではない理由（離散的な数値の後続要素に依存すること、安全な最大整数において定義域外の値を生成すること、文字列やカスタム比較関数に拡張できないこと）も説明します。
回答前の明確化のための質問
- 配列はすでにソートされていますか？ 本問題の設定では非減少順であることが保証されています。元のインデックスを保持したまま
未ソートの入力をソートすると、データモデルが変更され、全体の O(log n) の境界を満たせなくなります。
- 返すのは元のインデックスですか、ソート後のインデックスですか？ 入力がすでにソートされているため、ここでは同一です。
- 存在しないことは何で表しますか？ 本問題の設定では
[-1, -1]を返す必要があります。挿入ポイントが見つかっても、自動的に一致したとはみなせません。 - 重複値は許可されますか？ はい。重複が存在するからこそ、境界探索が必要になります。
- 配列は空である可能性がありますか？ はい。半開区間の実装であれば、いずれの終端も読み取ることなく処理できます。
- 数値の定義域は何ですか？ 値は JavaScript の安全な整数（safe integers）です。この解法では
target + 1を計算しないため、
境界を見つけるためだけに定義域外の番兵値を捏造することはありません。
- 二分探索を実装する必要がありますか？ この面接課題では実装が必要です。本番環境では、仕様が完全に一致している標準ライブラリの
関数を使用することが推奨されます。
- 入力を変更してもよいですか？ いいえ。また、どちらの境界探索も入力を変更する必要はありません。
30 秒回答フレームワーク
「1 つの一致を見つけてからスキャンするのではなく、2 つの境界探索を実行します。lowerBound は半開区間 [left, right) を探索して target 以上の最初の値を見つけ、upperBound は target より厳密に大きい最初の値を見つけます。各反復では middle = left + floor((right - left) / 2) を使用します。 中央値がターゲットの左側にある場合は left = middle + 1 を設定し、それ以外の場合は right = middle で中央値を保持します。 まず下限が範囲外であるか、またはターゲットと一致しないかを確認します。存在する場合、答えは [lower, upper - 1] となります。 2 回の探索を行っても計算量は O(log n) のままで、追加空間計算量は O(1) です。」
ステップバイステップの詳細解説
ステップ 1：「最初と最後」を 2 つの分割点として書き直す。
nums = [1, 2, 2, 2, 3] と target = 2 の場合：
lowerBound = 1 // first nums[i] >= 2
upperBound = 4 // first nums[i] > 2
answer = [1, 4 - 1] = [1, 3]この定義は、「左を探し続ける」「右を探し続ける」とするよりも検証が容易です。挿入ポイントは、ターゲットが存在しない場合でも 意味を持ちます。target = 4 の場合、両方とも配列長である 5 になりますが、これはターゲットが存在することを意味しません。 アルゴリズムは別途 nums[lower] === target を確認する必要があります。
ステップ 2：半開区間の不変条件を固定する。
各 lowerBound の反復の開始時において：
left未満のすべてのインデックスには、targetより厳密に小さい値が含まれる。right以上のすべてのインデックスには、target以上の値が含まれる。- 未確定の候補区間は
[left, right)である。
初期状態では left = 0 かつ right = nums.length であり、両方の外部領域は空であるため、不変条件が成り立ちます。 もし nums[middle] < target ならば、中央値およびその左側にあるものはすべて答えになり得ないため、left = middle + 1 と設定します。 そうでなければ、中央値は最初の有効な位置である可能性があるため残す必要があり、right = middle と設定します。
毎回の反復で区間は厳密に縮小します。left === right になったとき、未確定の要素は残りません。 左側にあるものはすべてより小さく、右側にあるものはすべてターゲット以上であるため、この位置が下限となります。
upperBound も異なる分割条件で同じ構造を使用します：
left未満のすべてのインデックスには、target以下の値が含まれる。right以上のすべてのインデックスには、targetより厳密に大きい値が含まれる。
したがって、nums[middle] <= target のときは left を進め、それ以外の場合は right を進めます。
ステップ 3：両方の境界関数を実装する。
function lowerBound(nums: number[], target: number): number {
let left = 0;
let right = nums.length;
while (left < right) {
const middle = left + Math.floor((right - left) / 2);
if (nums[middle] < target) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
}
function upperBound(nums: number[], target: number): number {
let left = 0;
let right = nums.length;
while (left < right) {
const middle = left + Math.floor((right - left) / 2);
if (nums[middle] <= target) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
}唯一の違いは比較条件です。明確に名前が付けられた 2 つの関数は、面接においてわかりにくいブール値のフラグを持った単一の関数よりも 説明しやすく、1 回限りの用途のために複雑な汎用抽象化を作成するのを避けることができます。
中央値は left + floor((right - left) / 2) で計算されるため、2 つの大きなインデックスを最初に加算することはありません。 JavaScript ランタイムの配列制限により、本問題でインデックスのオーバーフローが発生する可能性は低いですが、この式は固定長整数の言語にも安全に移植できます。
ステップ 4：結果を結合し、実際の一致を検証する。
function searchRange(nums: number[], target: number): [number, number] {
const first = lowerBound(nums, target);
if (first === nums.length || nums[first] !== target) {
return [-1, -1];
}
return [first, upperBound(nums, target) - 1];
}チェックの順序が重要です。nums[first] を読み取る前に first === nums.length をテストすることで、配列外の位置を要素として扱わないようにします。 first が一致することが確認できれば、上限は少なくとも first + 1 となり、1 を引くことで最後の出現位置が得られます。
上限を lowerBound(nums, target + 1) - 1 で代用しないでください。本問題の安全な整数の制約下では、正しい境界が返される可能性もありますが、 Number.MAX_SAFE_INTEGER に 1 を加算すると、正確な整数演算が保証される範囲を超えてしまいます。 入力が任意の JavaScript Number に拡張された場合、浮動小数点精度の関係で隣接する整数同士が同じ値に丸められることもあります。 文字列、BigInt 値、カスタム比較関数には普遍的な「次の値」が存在しません。 ターゲットより厳密に大きい最初の値を直接探索することが、完全な仕様を表現することになります。
ステップ 5：計算量を証明する。
各ループは長さ k の候補区間を最大でおよそ k / 2 に縮小するため、各境界関数は O(log n) 回の比較を実行します。 2 回の探索を行っても依然として O(log n) です。アルゴリズムは定数個のインデックスのみを保持し、 O(1) の追加空間を使用し、配列を変更しません。
任意の出現箇所を見つけてから外側にスキャンする方法では、[2, 2, ..., 2] の場合に全 n 要素を走査することになり、最悪計算量は O(n) になります。 事前計算されたハッシュテーブルを使用すれば繰り返しの検索は高速化されますが、構築に O(n) の時間と空間がかかります。 これは同じ静的入力に対して多数のクエリを実行する場合にのみ有用であり、与えられたソート済みという利点を無視しています。
ステップ 6：境界ケースとランダム化差分テストで検証する。
最低限、以下をカバーします：
| Input | target | Expected |
|---|---|---|
[] | 1 | [-1, -1] |
[5] | 5 | [0, 0] |
[5] | 4 | [-1, -1] |
[1, 2, 2, 2, 3] | 2 | [1, 3] |
[2, 2] | 2 | [0, 1] |
[1, 2, 3] | 0 | [-1, -1] |
[1, 2, 3] | 4 | [-1, -1] |
次に、重複を含むソート済み配列を生成し、その結果を線形探索の indexOf および lastIndexOf のベースラインと比較します。 線形アプローチは目標の計算量を満たしませんが、テストオラクル（正解判定基準）としては優れています。 固定ケースで既知の境界を確認し、ランダム化差分テストで特定の重複カウントや終端に関連するバグをあぶり出します。
質の高い模範解答
「配列はすでにソートされており、要件は O(log n) であるため、1 つのターゲットを見つけてから外側にスキャンすることはしません。すべてが重複要素の配列で線形時間になってしまうためです。私は答えを 2 つの挿入ポイントとして定義します。ターゲット以上の最初の値と、ターゲットより厳密に大きい最初の値です。
両方の探索で半開区間 [left, right) を使用します。左境界の場合、不変条件により left より前の要素はすべてターゲットより小さく、right 以降の要素はすべてターゲット以上となります。中央値がターゲットより小さい場合、答えは右側にあるはずなので left = middle + 1 とします。それ以外の場合、中央値が答えである可能性があるため right = middle とします。両者が一致した位置が下限となります。上限の探索では条件のみを変更し、ターゲット以下の値である場合に left を進めます。
まず下限を計算します。それが配列の長さに等しいか、またはターゲットを含んでいない場合は [-1, -1] を返します。そうでなければ、右端のインデックスは上限から 1 を引いたものになります。空の入力、存在しないターゲット、全重複、両端での一致もすべて同じロジックで処理されます。
各反復で区間が半分になるため、2 回の探索を行っても O(log n) であり、O(1) の追加空間を使用します。固定の境界ケースで検証した上で、ランダムなソート済み配列を indexOf および lastIndexOf と比較します。target + 1 は指定された定義域外の番兵値を作り出すことになり、他の順序付きドメインに汎用化できないため使用しません。」
よくある間違い
- 任意の出現箇所を見つけてから外側にスキャンする → すべて等しい配列で
O(n)になる → 下限と上限を個別に二分探索する。 - 一致した時点で即座にリターンする → 最左端や最右端ではなく任意の位置でヒットしてしまう → 境界を含んでいる可能性のある半分を保持する。
rightを配列の長さで初期化し、nums[right]を読み取る → 半開区間の終端にはアクセスできない →middleのみを読み取り、両端が一致した時点で終了する。left = middleで更新する → 2 要素の区間が永久に縮小しなくなる可能性がある → 中央値を除外するときはmiddle + 1を使用する。- 存在しないターゲットに対して挿入ポイントを返してしまう → 有効な挿入位置であっても一致したとは限らない → 境界と
nums[first] !== targetを確認する。 - 右境界に
target + 1を使用する → 定義域外または存在しない後続値に依存してしまう → ターゲットより厳密に大きい最初の位置を実装する。 - 閉区間と半開区間のテンプレートを混同する → 初期化、ループ条件、更新処理に矛盾が生じる → コードを書く前に区間のセマンティクスと不変条件を整理する。
- 中央の重複のみをテストする → 空の入力、両端の要素、一致しないケースで失敗する可能性がある → 境界テスト表とランダム化差分テストを追加する。
- ソートしてから探索しても依然として
O(log n)であると主張する → ソート処理が全体のコストを支配してしまう → 入力がソート済みであるという前提を活用するか、全体の計算量を再計算する。
フォローアップの質問と回答
フォローアップ 1: ターゲットが存在するかどうかを確認するだけであれば、2 回の探索は必要ですか？
いいえ。下限の探索を 1 回実行し、その位置が範囲内かつターゲットと等しいかどうかを確認するだけで済みます。計算量は O(log n) のままです。 標準ライブラリがまさにこの仕様を提供している場合、本番コードではそれを直接利用できます。2 回の探索が必要なのは、 重複範囲の両端を取得する場合のみです。
フォローアップ 2: 出現回数を返すにはどうすればよいですか？
ターゲットが存在する場合、個数は upperBound - lowerBound です。存在しない場合は 2 つの挿入ポイントが等しくなるため、 差も 0 になります。したがって、カウント専用の関数であれば配列の要素を読み取る必要すらありません。 2 つの境界の間にあるすべての要素がターゲットと等しいため、この式が成立します。
フォローアップ 3: 配列が降順にソートされている場合、何が変わりますか？
不変条件と比較条件を反転させます。降順での下限は「ターゲット以下の最初の値」となり、もう一方の境界は「ターゲットより厳密に小さい最初の値」となります。 元の比較条件を保持したまま最終的な解釈だけを反転させるようなことは避けてください。まず分割述語を定義し、 その真偽値に基づいて区間を更新します。
フォローアップ 4: 要素がオブジェクトであり、探索が特定のフィールドを使用する場合はどうなりますか？
createdAt のように、ソートされた比較キーに対して探索を行います。繰り返しクエリにおいてキーの抽出コストが高い場合は、 事前計算されたキー配列を保持します。Python のドキュメントでも、コストの高いキーはキャッシュまたは事前計算することが推奨されています。 探索中にオブジェクトシーケンスを変更してはなりません。変更するとソート済みの不変条件が崩れてしまいます。
フォローアップ 5: データがメモリ上ではなく、順序付きインデックスを持つデータベース内にある場合はどうしますか？
アプリケーション側の二分探索を多数のリモートクエリに変換してはなりません。ターゲットと等しい最小および最大の安定したソートキーの取得や、 インデックス範囲スキャンなど、データベースインデックスに範囲を特定させます。二分探索の反復ごとにネットワークラウンドトリップが発生すると、 O(log n) 回の比較が繰り返しの高レイテンシ呼び出しとなり、同時書き込み中に異なるスナップショットを参照してしまうリスクがあります。
フォローアップ 6: このテンプレートは「実現可能な最小の答え（最小値の最大化・最大値の最小化）」問題にどのように拡張できますか？
単調な述語（例えば、x 未満のすべての容量は実現不可能であり、ある値以上のすべての容量は実現可能であるなど）を定義します。 そして、暗黙的な解空間上で最初の真（true）となる述語に対して下限探索を行い、nums[middle] < target を !feasible(middle) に置き換えます。 述語が偽から真へと 1 回だけ遷移することが証明されている必要があります。真偽値が交互に現れる場合、二分探索の正当性の根拠は失われます。