Hello Algo探索章「二分探索演習」完全攻略──区間縮小のトレースから重複要素の境界、挿入位置の探索まで【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/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)1212 16なのでi 4とする2(4, 6, 5)2323 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)/2$ です。これはよくある $m (ij)/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 在区间 [m1, 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 の左端境界である」と主張しました。この生徒の説明は正しいですか数値 2 の左端境界と右端境界はそれぞれどこですか理由も説明してください。左端境界を探索するとき、中点の要素が目的の値と等しい場合、次はどちら側を探索すべきですか右端境界を探索するときはどちら側を探索すべきですか方向のみでよい解答と解説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 在区间 [m1, 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つの場面に適した方法を選び、理由を説明してください。ソート済みで今後変更されない $10^7$ 個の整数を繰り返し探索する。他のデータ構造は追加で作らない。挿入と削除が頻繁に行われるデータ集合で、あるキーが存在するかを繰り返し判定する。順序を保つ必要も範囲探索の必要もない。ソートされていない配列から、ある値を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 系問題としても出題されている定番内容です。解法のヒント演習より最初の区間はleft 0、right n - 1とし、区間が空でない条件はleft right。中点はmid left (right - left) // 2で計算する。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 在区间 [m1, 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 - 1i, j 0, nループ継続条件i ji jnums[m] target時の縮小j m - 1j m区間が空になる条件i ji j両閉区間は左右のポインタ操作が対称でミスを犯しにくいため、二分探索の章では両閉区間の書き方が推奨されています。C 実装では両パターンが binary_search.c のbinarySearchとbinarySearchLCROとして対照的に確認できます。プログラミング演習2ソート済み配列への挿入位置問題重複のない昇順整数配列numsと目的の値targetが与えられます。targetがすでに配列にあれば、そのインデックスを返す。なければ、targetを挿入しても重複のない昇順を保てる位置挿入位置を返す。答えが0になる場合も、配列の長さnに等しくなる場合もあります。二分探索を使って求めてくださいLeetCode の Search Insert Position 系問題としても出題されている内容です。解法のヒント演習より答えは 0 の場合も、配列の長さ n の場合もある先頭挿入と末尾挿入を忘れない。両閉区間を使う場合、nums[mid] targetならright mid - 1としてさらに左の位置を調べる。そうでなければleft mid 1。ループ終了時点で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 なら [m1, 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・縮小im1 / jm-1演習2挿入位置nums[m] targetで右端を詰め、終了時のiが挿入位置。左端探索の土台ここまで解き終えたら、ぜひ実際のコードを動かして確認してみてください。『Hello Algo』リポジトリの探索章コードは Python のほか、Java、C、C、Go、Rust など複数言語で収録されており、言語ごとの型の扱い整数オーバーフローの有無などを比較しながら読むと理解がさらに深まります。コードを実行したあとは、左閉右開区間での挿入位置探索への書き換えや、二分探索の境界で紹介されている「target 1の最左を探して右端を求める」変換テクニックにも挑戦し、探索アルゴリズム再考の比較表を頭に入れた上で、実データに対して「どの探索を使うべきか」を判断できる状態を目指しましょう。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Hello Algo探索章「二分探索演習」完全攻略──区間縮小のトレースから重複要素の境界、挿入位置の探索まで
Hello Algo探索章「二分探索演習」完全攻略──区間縮小のトレースから重複要素の境界、挿入位置の探索まで【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/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)1212 16なのでi 4とする2(4, 6, 5)2323 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)/2$ です。これはよくある $m (ij)/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 在区间 [m1, 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 の左端境界である」と主張しました。この生徒の説明は正しいですか数値 2 の左端境界と右端境界はそれぞれどこですか理由も説明してください。左端境界を探索するとき、中点の要素が目的の値と等しい場合、次はどちら側を探索すべきですか右端境界を探索するときはどちら側を探索すべきですか方向のみでよい解答と解説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 在区间 [m1, 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つの場面に適した方法を選び、理由を説明してください。ソート済みで今後変更されない $10^7$ 個の整数を繰り返し探索する。他のデータ構造は追加で作らない。挿入と削除が頻繁に行われるデータ集合で、あるキーが存在するかを繰り返し判定する。順序を保つ必要も範囲探索の必要もない。ソートされていない配列から、ある値を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 系問題としても出題されている定番内容です。解法のヒント演習より最初の区間はleft 0、right n - 1とし、区間が空でない条件はleft right。中点はmid left (right - left) // 2で計算する。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 在区间 [m1, 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 - 1i, j 0, nループ継続条件i ji jnums[m] target時の縮小j m - 1j m区間が空になる条件i ji j両閉区間は左右のポインタ操作が対称でミスを犯しにくいため、二分探索の章では両閉区間の書き方が推奨されています。C 実装では両パターンが binary_search.c のbinarySearchとbinarySearchLCROとして対照的に確認できます。プログラミング演習2ソート済み配列への挿入位置問題重複のない昇順整数配列numsと目的の値targetが与えられます。targetがすでに配列にあれば、そのインデックスを返す。なければ、targetを挿入しても重複のない昇順を保てる位置挿入位置を返す。答えが0になる場合も、配列の長さnに等しくなる場合もあります。二分探索を使って求めてくださいLeetCode の Search Insert Position 系問題としても出題されている内容です。解法のヒント演習より答えは 0 の場合も、配列の長さ n の場合もある先頭挿入と末尾挿入を忘れない。両閉区間を使う場合、nums[mid] targetならright mid - 1としてさらに左の位置を調べる。そうでなければleft mid 1。ループ終了時点で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 なら [m1, 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・縮小im1 / jm-1演習2挿入位置nums[m] targetで右端を詰め、終了時のiが挿入位置。左端探索の土台ここまで解き終えたら、ぜひ実際のコードを動かして確認してみてください。『Hello Algo』リポジトリの探索章コードは Python のほか、Java、C、C、Go、Rust など複数言語で収録されており、言語ごとの型の扱い整数オーバーフローの有無などを比較しながら読むと理解がさらに深まります。コードを実行したあとは、左閉右開区間での挿入位置探索への書き換えや、二分探索の境界で紹介されている「target 1の最左を探して右端を求める」変換テクニックにも挑戦し、探索アルゴリズム再考の比較表を頭に入れた上で、実データに対して「どの探索を使うべきか」を判断できる状態を目指しましょう。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考