Hello Algo探索章「二分探索演習」完全攻略──区間縮小のトレースから重複要素の境界、挿入位置の探索まで

本記事は、オープンソースのデータ構造・アルゴリズム教材『Hello Algo』日本語版の探索章に収録された演習問題（確認問題3問＋プログラミング演習2問）を、正解・解説・リポジトリ内の実装コード付きで体系的に解説する技術ガイドです。二分探索の区間の狭め方を手で追跡し、重複要素の左右境界と挿入位置の求め方、そして線形探索・二分探索・ハッシュテーブルの使い分け判断力を、実データを使って身に付けられます。

演習の全体像と前提知識

探索（サーチ）は「データ構造の中から条件を満たす要素を特定する」操作であり、探索アルゴリズム再考の章では、実装思想の違いによって次の2系統に整理されます。

• 総当たり探索：線形探索、幅優先探索（BFS）、深さ優先探索（DFS）など、データ構造を走査して目標を特定する系統。
• 適応的探索：二分探索・ハッシュ探索・木探索など、データの「整列済み」といった事前情報や追加構造を利用して高速に特定する系統。

本章の演習は、このうち特に二分探索の仕組み理解を問う「確認問題」と、実装力を問う「プログラミング演習」の2部構成です。取り組む前に、以下の各章ページで基本を復習しておくと効果的です。

関連する章ページ	学べる内容
二分探索	両閉区間・左閉右開区間の基本アルゴリズムと $O(\log n)$ の導出
二分探索の挿入位置	挿入位置の探索と重複要素への拡張
二分探索の境界	重複要素の左端・右端の探索
探索アルゴリズム再考	探索手法の全体俯瞰と効率比較表
まとめ	探索章全体の要点の振り返り

確認問題1：二分探索による区間の狭め方をトレースする

問題

ソート済み配列 [2, 5, 8, 12, 16, 23, 38] から値 16 を二分探索で探します。両閉区間 $[i, j]$ を使い、中点を $m = i + (j-i)/2$（小数点以下切り捨て）と定義したとき、目的の値が見つかるまでの各回の (i, j, m)、中点の要素、次の区間の狭め方を書き出してください。

解答と解説

各回の探索過程は下表のとおりです。

回	(i, j, m)	中点の要素	次の操作
1	(0, 6, 3)	12	12 < 16 なので i = 4 とする
2	(4, 6, 5)	23	23 > 16 なので j = 4 とする
3	(4, 4, 4)	16	目的の値を発見し、インデックス 4 を返す

配列はソート済みであるため、中点の値が目的の値より小さければ中点とその左側を除外でき（i = m + 1）、大きければ中点とその右側を除外できます（j = m - 1）。3回目の判定で区間が (4, 4) のただ1要素にまで縮小し、nums[4] == 16 を確認して探索が終了します。

中点計算式の注意点

本問で与えられている中点式は $m=i+(j-i)\mathrm{/}2$ です。これはよくある $m=(i+j)\mathrm{/}2$ と等価ですが、C や Java など固定精度の整数型では i + j が int 型の最大値を超えてオーバーフローするリスクがあるため、実際のコードでは引き算ベースの式が使われます。リポジトリの C 実装 binary_search.c でも、この点を踏まえて次のように書かれています。

int binarySearch(int *nums, int len, int target) {
    // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    int i = 0, j = len - 1;
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target)       // target 在区间 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target)  // target 在区间 [i, m-1] 中
            j = m - 1;
        else
            return m;               // 找到目标元素，返回其索引
    }
    return -1;                      // 未找到目标元素，返回 -1
}

一方、Python は整数が任意精度のため、binary_search.py では m = (i + j) // 2 と直接計算できます。どの言語でもループ1回につき区間が半分になるため、反復回数は $\log_2 n$ 回に収まり、時間計算量 $O(\log n)$・空間計算量 $O(1)$ というのが二分探索の核心的な性質です。

確認問題2：重複要素の左右の境界を探る

問題

配列 [1, 2, 2, 2, 4, 6] から数値 2 を探索します。ある生徒は二分探索でまずインデックス 2 に 2 を見つけて即座に返し、「インデックス 2 が数値 2 の左端境界である」と主張しました。

1. この生徒の説明は正しいですか？数値 2 の左端境界と右端境界はそれぞれどこですか？理由も説明してください。
2. 左端境界を探索するとき、中点の要素が目的の値と等しい場合、次はどちら側を探索すべきですか？
3. 右端境界を探索するときはどちら側を探索すべきですか（方向のみでよい）？

解答と解説

1. 説明は正しくありません。 配列中に 2 が 3 個あり、インデックス 2 はそのうちの中央です。1 個の 2 を見つけて即座に返す方法では「いずれかの 2 を見つけた」ことしか保証できず、「最も左」や「最も右」の 2 であるとは限りません。この配列では左端境界はインデックス 1、右端境界はインデックス 3 です。

2. 左端境界を探索するときは、中点の要素が 2 と等しくても引き続き左側を探索します。両閉区間を使う場合は、等しいときに j = m - 1 として右端を詰めます。これにより、ポインタ $i$ は最終的に「最も左の 2」を指し、ポインタ $j$ は「2 より小さい最も右の要素」を指します。

3. 右端境界を探索するときは、中点の要素が 2 と等しければ引き続き右側を探索し、i = m + 1 とします。対称的な操作で、最終的に $j$ が「最も右の 2」を指します。

実装の裏付け：挿入位置探索への帰着

この「等しい場合にも区間を詰め続ける」という発想は、リポジトリの binary_search_insertion.py に明快に実装されています。重複要素がある配列では、nums[m] == target のときも j = m - 1 に縮小することで、ループ終了後の $i$ が最左の target の挿入位置を指すのです。

def binary_search_insertion(nums: list[int], target: int) -> int:
    """二分查找插入点（存在重复元素）"""
    i, j = 0, len(nums) - 1  # 初始化双闭区间 [0, n-1]
    while i <= j:
        m = (i + j) // 2  # 计算中点索引 m
        if nums[m] < target:
            i = m + 1     # target 在区间 [m+1, j] 中
        elif nums[m] > target:
            j = m - 1     # target 在区间 [i, m-1] 中
        else:
            j = m - 1     # 最右一个小于 target 的元素在区间 [i, m-1] 中
    return i  # 返回插入点 i

さらに binary_search_edge.py は、この関数を左端・右端の探索に再利用しています。

def binary_search_left_edge(nums: list[int], target: int) -> int:
    """二分查找最左一个 target"""
    i = binary_search_insertion(nums, target)
    if i == len(nums) or nums[i] != target:
        return -1   # 未找到 target
    return i

def binary_search_right_edge(nums: list[int], target: int) -> int:
    """二分查找最右一个 target（转化为查找最左一个 target + 1）"""
    i = binary_search_insertion(nums, target + 1)
    j = i - 1
    if j == -1 or nums[j] != target:
        return -1   # 未找到 target
    return j

ここで重要なのは「探索区間の縮小 = ポインタ $i$, $j$ に探索目標を設定すること」という視点です。目標は「特定の要素」である場合も、「target より小さい要素」のような要素の範囲である場合もあります。等しいときの分岐先を変えるだけで、同じ二分探索の骨格から挿入位置・左端・右端のすべてが導けることを、この演習は問いかけています。詳細は二分探索の挿入位置と二分探索の境界の章を参照してください。

確認問題3：データ特性に応じた探索手法の選び方

問題

「線形探索・二分探索・ハッシュテーブル」から、次の3つの場面に適した方法を選び、理由を説明してください。

1. ソート済みで今後変更されない $10^7$ 個の整数を繰り返し探索する。他のデータ構造は追加で作らない。
2. 挿入と削除が頻繁に行われるデータ集合で、あるキーが存在するかを繰り返し判定する。順序を保つ必要も範囲探索の必要もない。
3. ソートされていない配列から、ある値を1回だけ探索する。

解答と解説

1. 二分探索を選びます。 データがソート済みで今後変更されないため、追加の空間を一切使わずに各探索を $O(\log n)$ で行えます。$10^7 \approx 2^{23.25}$ なので、1回あたり約24回の比較で探索が完了します。追加のデータ構造を作れないという制約も、追加領域 $O(1)$ の二分探索なら問題になりません。

2. ハッシュテーブルを選びます。 ハッシュ関数によってキーが各バケットへほぼ均等に分散される場合、挿入・削除・キーによる存在判定の平均時間計算量はいずれも $O(1)$ になります。順序を保つ必要や範囲探索の必要がないため、データの順序性を維持できないというハッシュテーブルの弱点が問題になりません。

3. 先頭から末尾まで直接走査する線形探索を選びます。 1回しか探索しない場合、二分探索のためのソート（$O(n \log n)$）やハッシュテーブルの構築（$O(n)$）でも、最初に配列全体を処理する必要があります。この1回の処理に必要な作業の総量は、直接走査の $O(n)$ よりもむしろ増えてしまいます。

判断の観点

どの方法を選ぶかは、次の要素の掛け合わせで決まります。

• データがソート済みかどうか
• 追加のデータ構造を作れるかどうか
• 探索回数（1回だけか、繰り返しか）
• 必要な操作の種類（存在判定だけか、挿入・削除・範囲探索も必要か）

探索アルゴリズム再考の章では、この判断を一般化した効率比較表が掲載されており、線形探索（要素探索 $O(n)$・前処理不要）、二分探索（要素探索 $O(\log n)$・ソート前処理 $O(n\log n)$・追加領域 $O(1)$）、木探索・ハッシュ探索（$O(\log n)$/$O(1)$・追加構造の維持コストあり）のトレードオフを一覧できます。ハッシュで線形探索を置き換える $O(n)\to O(1)$ の高速化戦略については、ハッシュによる線形探索の置き換えの章で具体例（two_sum.py など）とともに解説されています。

プログラミング演習1：ソート済み配列の二分探索

問題

重複のない昇順整数配列 nums と目的の値 target が与えられます。二分探索を使って target を探し、存在すればその配列インデックスを、存在しなければ -1 を返す関数を実装してください（LeetCode の Binary Search 系問題としても出題されている定番内容です）。

解法のヒント（演習より）

1. 最初の区間は left = 0、right = n - 1 とし、区間が空でない条件は left <= right。
2. 中点は mid = left + (right - left) // 2 で計算する。
3. nums[mid] < target なら左端を mid + 1 へ、nums[mid] > target なら右端を mid - 1 へ移す。等しければ即座に返す。

解答コード

リポジトリの binary_search.py にある両閉区間版の実装は、そのまま本問の模範解答になります。

def binary_search(nums: list[int], target: int) -> int:
    """二分查找（双闭区间）"""
    i, j = 0, len(nums) - 1          # 初始化双闭区间 [0, n-1]
    while i <= j:                    # 当搜索区间为空（i > j）时跳出
        m = (i + j) // 2             # 计算中点索引 m
        if nums[m] < target:
            i = m + 1                # target 在区间 [m+1, j] 中
        elif nums[m] > target:
            j = m - 1                # target 在区间 [i, m-1] 中
        else:
            return m                 # 找到目标元素，返回其索引
    return -1                        # 未找到目标元素，返回 -1

動作確認用のドライバコードも同ファイルにあり、nums = [1, 3, 6, 8, 12, 15, 23, 26, 31, 35]、target = 6 に対してインデックス 2 が返ることを確認できます。

区間の表し方による違い

同じ機能は「左閉右開区間 $[0, n)$」でも実装でき、同ファイルの binary_search_lcro() がその例です。両者の違いは下表の3点に集約され、コードの初期化・ループ条件・区間の縮小操作がそれぞれ異なります。

項目	両閉区間 $[0, n-1]$	左閉右開区間 $[0, n)$
初期化	i, j = 0, n - 1	i, j = 0, n
ループ継続条件	i <= j	i < j
nums[m] > target 時の縮小	j = m - 1	j = m
区間が空になる条件	i > j	i == j

両閉区間は左右のポインタ操作が対称でミスを犯しにくいため、二分探索の章では両閉区間の書き方が推奨されています。C 実装では両パターンが binary_search.c の binarySearch と binarySearchLCRO として対照的に確認できます。

プログラミング演習2：ソート済み配列への挿入位置

問題

重複のない昇順整数配列 nums と目的の値 target が与えられます。

• target がすでに配列にあれば、そのインデックスを返す。
• なければ、target を挿入しても重複のない昇順を保てる位置（挿入位置）を返す。

答えが 0 になる場合も、配列の長さ n に等しくなる場合もあります。二分探索を使って求めてください（LeetCode の Search Insert Position 系問題としても出題されている内容です）。

解法のヒント（演習より）

1. 答えは 0 の場合も、配列の長さ n の場合もある（先頭挿入と末尾挿入を忘れない）。
2. 両閉区間を使う場合、nums[mid] >= target なら right = mid - 1 としてさらに左の位置を調べる。そうでなければ left = mid + 1。
3. ループ終了時点で left が挿入位置になっている。

解答コード

ヒント2の「等しいときも右端を詰める」流儀に従うと、次のように書けます。このループでは、nums[m] >= target のときに $j$ を左へ詰め続けるため、終了時の i は「target 以上の最初の要素」＝挿入位置を指します。重複がない配列なら、target が存在する場合はそのインデックスと一致します。

def search_insert(nums: list[int], target: int) -> int:
    i, j = 0, len(nums) - 1
    while i <= j:
        m = (i + j) // 2
        if nums[m] >= target:   # target は [i, m-1] 側にある
            j = m - 1
        else:                   # nums[m] < target なら [m+1, j] 側
            i = m + 1
    return i                    # ループ終了時、i が挿入位置

挿入位置探索が「左端探索」の土台になる

なお、リポジトリの binary_search_insertion.py は、重複がない場合を binary_search_insertion_simple()、重複がある場合を binary_search_insertion() の2関数で提供しており、ドライバコードで次のように検証できます。

# 无重复元素的数组
nums = [1, 3, 6, 8, 12, 15, 23, 26, 31, 35]
# target = 6  → 插入点索引 2 / target = 9 → 插入点索引 4

# 包含重复元素的数组
nums = [1, 3, 6, 6, 6, 6, 6, 10, 12, 15]
# target = 2 → 插入点 1 / target = 6 → 插入点 2（最左の 6）/ target = 20 → 插入点 10（末尾）

確認問題2でも触れたとおり、重複要素を持つ配列の挿入位置は「最左の target」そのものであり、二分探索の境界の章では、この性質を利用して左端境界 binary_search_left_edge() が実装されています。つまり本演習2は、二分探索を「要素の探索」から「挿入位置の探索」へ一般化する、探索章の要となる練習問題なのです。

演習の復習と次のステップ

本記事で扱った5問の要点を整理します。

演習	要点
確認問題1（区間のトレース）	中点の大小判定で区間を半分に縮小。$m = i + (j-i)/2$ でオーバーフロー回避。 $O(\log n)$ 回で終了
確認問題2（左右境界）	等しい要素を1つ見つけても左右の境界は保証されない。左端は j = m - 1、右端は i = m + 1 で詰める
確認問題3（手法の選択）	ソート済み静的データ＝二分探索、頻繁更新＝ハッシュ、1回だけ＝線形走査
演習1（二分探索）	両閉区間 [0, n-1]・ループ条件 i <= j・縮小 i=m+1 / j=m-1
演習2（挿入位置）	nums[m] >= target で右端を詰め、終了時の i が挿入位置。左端探索の土台

ここまで解き終えたら、ぜひ実際のコードを動かして確認してみてください。『Hello Algo』リポジトリの探索章コードは Python のほか、Java、C、C++、Go、Rust など複数言語で収録されており、言語ごとの型の扱い（整数オーバーフローの有無など）を比較しながら読むと理解がさらに深まります。コードを実行したあとは、左閉右開区間での挿入位置探索への書き換えや、二分探索の境界で紹介されている「target + 1 の最左を探して右端を求める」変換テクニックにも挑戦し、探索アルゴリズム再考の比較表を頭に入れた上で、実データに対して「どの探索を使うべきか」を判断できる状態を目指しましょう。