C++で2次元行列を効率的に検索する方法

m × n の行列の中から特定の値を効率的に検索するアルゴリズムを考えます。この行列には、次のような性質があります。

• 各行は左から右に向かって昇順にソートされている
• 各行の先頭の数値は、直前の行の最後の整数よりも大きい

例えば、行列が次のような場合を考えてみましょう。

このとき、検索対象の値が 16 であれば、出力は True になります。

アルゴリズムの考え方

この問題は「2段階の二分探索」によって解くことができます。まず行方向の二分探索で、ターゲット値が存在しうる行を特定し、次にその行の中で列方向の二分探索を行います。計算量は O(log m + log n) となり、全要素を線形に走査する O(m × n) よりも大幅に高速です。

具体的な手順は以下の通りです。

• n := 行数(n が 0 なら false を返す)、m := 列数(m が 0 なら false を返す)
• low := 0、high := n − 1 とする
• low < high の間、次を繰り返す
  • mid := low + (high − low + 1) / 2
  • mat[mid][0] <= target なら low := mid、そうでなければ high := mid − 1
• rlow := 0、rhigh := m − 1、ans := 0 とする
• rlow <= rhigh の間、次を繰り返す
  • mid := rlow + (rhigh − rlow) / 2
  • mat[low][mid] == target なら ans := 1 としてループを抜ける
  • matrix[low][mid] < target なら rlow := mid + 1
  • それ以外の場合は rhigh := mid − 1
• ans を返す

理解を深めるために、以下の実装例を見てみましょう。

実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        lli n,m;
        n = matrix.size();
        if(!n)return false;
        m = matrix[0].size();
        if(!m)return false;
        lli low = 0, high = n-1;
        while(low<high){
            lli mid = low + ( high - low +1)/2;
            if(matrix[mid][0]<=target)low = mid;
            else high = mid -1;
        }
        lli rlow = 0, rhigh = m-1;
        lli ans = 0;
        while(rlow<=rhigh){
            lli mid = rlow+(rhigh - rlow)/2;
            if(matrix[low][mid] == target){
                ans =1;
                break;
            }else if(matrix[low][mid]<target)rlow=mid+1;
            else rhigh= mid-1;
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{1,3,5,7},{10,11,16,20},{23,30,34,50},{53,62,78,98}};
    cout << ob.searchMatrix(v, 16);
}

入力

[[1,3,5,7],[10,11,16,20],[23,30,34,50],[53,62,78,98]]
16

出力

1

この実装では、まず各行の先頭要素を比較してターゲットが属する行を絞り込み、続いてその行内で通常の二分探索を行うことで、値の存在を効率的に判定しています。行列が空の場合や行・列が 0 の場合も適切に処理されるため、堅牢な実装となっています。