分割統治探索戦略¶
私たちはすでに学んだように、探索アルゴリズムは大きく二つに分けられる。
- 力ずく探索：データ構造を走査することで実現され、時間計算量は \(O(n)\) である。
- 適応的探索：固有のデータ構造や事前情報を利用し、時間計算量は \(O(\log n)\) 、さらには \(O(1)\) に達しうる。
実際、時間計算量が \(O(\log n)\) の探索アルゴリズムは通常、分割統治戦略に基づいて実装される。たとえば二分探索や木構造である。
- 二分探索の各ステップでは、問題（配列内で目標要素を探索すること）を小さな問題（配列の半分で目標要素を探索すること）に分解し、この過程は配列が空になるか目標要素が見つかるまで続く。
- 木構造は分割統治の考え方を代表するものであり、二分探索木、AVL 木、ヒープなどのデータ構造では、さまざまな操作の時間計算量はいずれも \(O(\log n)\) である。
二分探索の分割統治戦略は以下のとおりである。
- 問題は分解できる：二分探索は、元の問題（配列内で探索すること）を部分問題（配列の半分で探索すること）へ再帰的に分解する。これは中央要素と目標要素を比較することで実現される。
- 部分問題は独立している：二分探索では、各ラウンドで一つの部分問題だけを処理し、ほかの部分問題の影響を受けない。
- 部分問題の解を統合する必要はない：二分探索は特定の要素を探すことを目的としているため、部分問題の解を統合する必要がない。部分問題が解決されると、元の問題も同時に解決される。
分割統治が探索効率を高められる本質的な理由は、力ずく探索では各ラウンドで一つの候補しか除外できないのに対し、**分割統治による探索では各ラウンドで候補の半分を除外できる**からである。
分割統治に基づく二分探索¶
前の章では、二分探索を漸化式（反復）に基づいて実装した。ここでは分割統治（再帰）に基づいてこれを実装する。
Question
長さ \(n\) の昇順配列 nums が与えられ、そのすべての要素は一意である。要素 target を探索せよ。
分割統治の観点から、探索区間 \([i, j]\) に対応する部分問題を \(f(i, j)\) と記す。
元の問題 \(f(0, n-1)\) を出発点として、次の手順で二分探索を行う。
- 探索区間 \([i, j]\) の中点 \(m\) を計算し、それに基づいて探索区間の半分を除外する。
- 規模が半分に縮小された部分問題を再帰的に解く。候補は \(f(i, m-1)\) または \(f(m+1, j)\) である。
1.と2.の手順を繰り返し、targetが見つかるか区間が空になったら返す。
次の図は、配列内で要素 \(6\) を二分探索する分割統治の過程を示している。
実装コードでは、再帰関数 dfs() を宣言して問題 \(f(i, j)\) を解く。