m x n のソート済み2次元行列から特定のターゲット値を効率的に探索するアルゴリズムについて考察します。
この行列は、以下の特殊な特性を持っています。
- 各行の要素は左から右へ昇順に並んでいます。
- 各列の要素は上から下へ昇順に並んでいます。
この特性を最大限に活用することで、ブルートフォース探索（O(mn)）を避け、O(m+n)という線形的な時間計算量で高速な検索を実現できます。空間計算量はO(1)です。
問題解決のアプローチ
行列の持つ昇順ソート特性を考慮すると、最適な戦略は、行列の右上隅（または左下隅）から探索を開始することです。この出発点を利用することで、比較ごとに確実に1行または1列を探索範囲から除外できます。
右上隅からの探索ロジック
- 探索開始位置を右上隅 (0行目、最終列) に設定します。
- 現在の要素がターゲット値と一致する場合、要素が見つかったので
trueを返します。 - 現在の要素がターゲット値より大きい場合、ターゲットは現在の列には存在しないため、探索範囲を左に移動します（列インデックスをデクリメント）。
- 現在の要素がターゲット値より小さい場合、ターゲットは現在の行には存在しないため、探索範囲を下に移動します（行インデックスをインクリメント）。
- 行または列のインデックスが行列の境界を超えた場合、ターゲットは見つからなかったため
falseを返します。
C++による実装例
上記のロジックに基づいたC++コードの完全な実装を以下に示します。
#include <vector>
#include <iostream>
// 行と列がそれぞれ昇順にソートされた2次元行列を探索するクラス
class MatrixFinder {
public:
// 指定されたターゲット値を行列から検索します
bool findTargetInMatrix(const std::vector<std::vector<int>>& grid, int targetValue) {
// 行列が空であるか、最初の行が空である場合は、ターゲットは存在しえない
if (grid.empty() || grid[0].empty()) {
return false;
}
const int totalRows = grid.size();
const int totalCols = grid[0].size();
// 探索開始位置を右上隅に設定します
// この位置の要素は、現在の行で最大値を持つ可能性があり、現在の列で最小値を持つ可能性があるため、
// ターゲット値との比較によって効率的に探索範囲を絞り込むことができます。
int currentRowIndex = 0;
int currentColIndex = totalCols - 1;
// 行の範囲内 (0 から totalRows-1) かつ列の範囲内 (0 から totalCols-1) である限り探索を続ける
while (currentRowIndex < totalRows && currentColIndex >= 0) {
int currentValue = grid[currentRowIndex][currentColIndex];
if (currentValue == targetValue) {
// ターゲット値が見つかった
return true;
} else if (currentValue > targetValue) {
// 現在の値がターゲットよりも大きい場合、ターゲットは現在の列の左側に存在する可能性がある。
// または、現在の列にはターゲットが存在しないため、左の列へ移動。
currentColIndex--;
} else { // currentValue < targetValue
// 現在の値がターゲットよりも小さい場合、ターゲットは現在の行の下側に存在する可能性がある。
// または、現在の行にはターゲットが存在しないため、下の行へ移動。
currentRowIndex++;
}
}
// 行列全体を探索したがターゲット値が見つからなかった
return false;
}
};
// テストコード
int main() {
std::vector<std::vector<int>> testGrid = {
{1, 4, 7, 11, 15},
{2, 5, 8, 12, 19},
{3, 6, 9, 16, 22},
{10, 13, 14, 17, 24},
{18, 21, 23, 26, 30}
};
MatrixFinder finder;
int existingTarget = 5; // 行列内に存在するターゲット
int missingTarget = 20; // 行列内に存在しないターゲット
std::cout << std::boolalpha; // true/false を出力するために設定
std::cout << "ターゲット " << existingTarget << " の探索結果: "
<< finder.findTargetInMatrix(testGrid, existingTarget) << std::endl;
std::cout << "ターゲット " << missingTarget << " の探索結果: "
<< finder.findTargetInMatrix(testGrid, missingTarget) << std::endl;
return 0;
}
アルゴリズムの主要なポイント
- 境界値の確認: 最初に、行列が空でないか、またはその最初の行が空でないかを確認し、無効なアクセスを防止します。
- 探索開始位置: 探索は常に右上隅の要素から開始します (
grid[0][cols-1])。 - 探索ロジック:
- 現在の要素がターゲットと一致すれば、ただちに
trueを返します。 - 現在の要素がターゲットより大きい場合、ターゲットは現在の列には存在しないため、列インデックスをデクリメントして左に移動します。
- 現在の要素がターゲットより小さい場合、ターゲットは現在の行には存在しないため、行インデックスをインクリメントして下に移動します。
- 現在の要素がターゲットと一致すれば、ただちに
- 探索終了条件: 行インデックスが総行数を超過するか、列インデックスが0未満になった場合、ターゲットは見つからなかったと判断し、
falseを返します。
計算量の分析
- 時間計算量: O(m + n)
最悪の場合、探索パスは行列の1行と1列を横断します。したがって、最大でm回の行移動とn回の列移動が発生するため、全体の計算量は行数mと列数nの合計に比例します。
- 空間計算量: O(1)
アルゴリズムは探索に数個の変数しか使用せず、入力行列のサイズに比例する追加のメモリは使用しません。
このアプローチは、ブルートフォース探索（O(mn)）と比較して大幅に効率的であり、追加の空間を必要としないため、ソート済み2次元行列の探索における標準的な最適解とされています。