C++で1の数が最も多い行を見つけるアルゴリズム

この問題では、各行の要素が昇順にソートされたバイナリ行列（0と1のみで構成される行列）が与えられます。私たちの課題は、1の数が最も多い行を見つけることです。

問題の例

入力：

mat[][] = {{0 1 1 1}
   {1 1 1 1}
   {0 0 0 1}
   {0 0 1 1}}

出力：

1

説明：

行列の各行に含まれる1の個数：
行 0 ： 3
行 1 ： 4
行 2 ： 1
行 3 ： 2

解法アプローチ

この問題に対するシンプルな解決策は、「最初の1が出現するインデックスが最小の行」を見つけることです。各行はソートされているため、最初の1の位置さえ分かれば、その行に含まれる1の総数を即座に計算できます。

一つ目のアプローチは、行ごとの線形走査です。各行を先頭から順に調べて最初の1のインデックスを特定し、その情報をもとに1の数が最大の行を返します。

もう一つのより効率的なアプローチは、二分探索（binary search）を利用して、各行における最初の1の出現位置を求める方法です。二分探索を使うことで、時間計算量は O(R log C) となり、大規模な行列でも高速に処理できます。

実装例

以下は、二分探索を用いた解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;
#define R 4
#define C 4
int findFirst1BinSearch(bool arr[], int low, int high){
   if(high >= low){
      int mid = low + (high - low)/2;
      if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
         return mid;
      else if (arr[mid] == 0)
         return findFirst1BinSearch(arr, (mid + 1), high);
      else
         return findFirst1BinSearch(arr, low, (mid -1));
   }
   return -1;
}
int findMaxOneRow(bool mat[R][C]){
   int max1RowIndex = 0, max = -1;
   for (int i = 0; i < R; i++){
      int first1Index = findFirst1BinSearch(mat[i], 0, C-1);
      if (first1Index != -1 && C-first1Index > max){
         max = C - first1Index;
         max1RowIndex = i;
      }
   }
   return max1RowIndex;
}
int main(){
   bool mat[R][C] = { {0, 1, 1, 1},
   {1, 1, 1, 1},
   {0, 0, 1, 1},
   {0, 0, 0, 1}};
   cout<<"The row with maximum number of 1's in the matrix is "<<findMaxOneRow(mat);
   return 0;
}

出力結果

The row with maximum number of 1's in the matrix is 1

このように、各行に対して二分探索を実行し、最初の1のインデックスから1の個数（C − インデックス）を算出することで、最も多くの1を含む行を効率的に特定できます。