C++で0と1の無限ソート済み配列から最初の1のインデックスを見つける方法

問題概要

この問題では、ブール値（0と1のみ）がソートされた順序で格納された無限配列 bin[] が与えられます。私たちのタスクは、この無限ソート済み配列の中で最初の1が出現するインデックスを見つけることです。

ここでいう「無限配列」とは、配列の長さに上限がなく、かつ配列内に必ず1が存在することが保証されているという意味です。

問題を理解するための例

入力 : bin[] = {0, 0, 0, 1, 1, ....}
出力 : 3

説明：

バイナリ配列において、最初の1はインデックス3の位置に出現します。

解決アプローチ

この問題を解くには、配列内で最初の1が出現するインデックスを見つける必要があります。そのために利用できる探索手法を2つ紹介します。

アプローチ1：線形探索

最もシンプルな方法は線形探索です。無限ループを使って配列を先頭から順に走査し、最初に1が見つかった時点でそのインデックスを返します。

計算量は O(n) となり、1の位置が後ろにあるほど時間がかかる点が弱点ですが、実装は非常に簡単です。

サンプルコード（線形探索）

#include <iostream>
using namespace std;

int find1stOneInfiniteArray(int bin[]) {
   int i = 0;
   while(1){
      if (bin[i] == 1)
         return i;
      i++;
   }
   return -1;
}

int main() {
   int bin[] = { 0, 0, 0, 1, 1, 1 };
   cout<<"無限配列で最初の1が出現するインデックスは "<<find1stOneInfiniteArray(bin);
   return 0;
}

出力結果

無限配列で最初の1が出現するインデックスは 3

アプローチ2：二分探索（より効率的）

配列がソートされているため、二分探索を活用することで計算量を O(log n) まで削減できます。

ただし、通常の二分探索には上下限（low と high）が必要です。無限配列には上限がないため、まず指数探索の考え方を使って境界を決定します。具体的には、high の値を1から始めて、bin[high] が1になるまで2倍ずつ増やしていきます。こうして得られた low と high の範囲に対して二分探索を実行すれば、最初の1のインデックスを効率よく見つけられます。

サンプルコード（二分探索）

#include <iostream>
using namespace std;

int find1stOneInfiniteArray(int bin[], int low, int high) {
   int mid;
   while (low <= high) {
      mid = (low + high) / 2;
      if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0))
         return mid;
      else if (bin[mid] == 1)
         high = mid - 1;
      else
         low = mid + 1;
   }
   return -1;
}

int main() {
   int bin[] = { 0, 0, 0, 1, 1, 1, 1 };
   int low = 0;
   int high = 1;
   // 1が見つかるまでhighを2倍ずつ拡大して範囲を決定
   while(bin[high] != 1){
      low = high;
      high *= 2;
   }
   cout<<"無限配列で最初の1が出現するインデックスは " <<find1stOneInfiniteArray(bin,low, high);
   return 0;
}

出力結果

無限配列で最初の1が出現するインデックスは 3

まとめ

無限ソート済み配列から最初の1を見つける問題では、単純な線形探索でも解けますが、配列がソートされている特性を活かし、指数探索で範囲を絞ってから二分探索を行うことで、O(log n) の効率的な解法が実現できます。実際の開発や競技プログラミングでは、後者のアプローチが推奨されます。