C++でソートされた0と1の配列から最初の「1」のインデックスを効率的に検索する方法

この問題では、ブール値（0と1のみ）で構成され、昇順にソートされた配列 bin[] が与えられます。求められるのは、配列内で最初に現れる「1」のインデックスを見つけることです。

問題の例

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

説明： ソート済みバイナリ配列の中で、最初に「1」が出現するのはインデックス3の位置です。

解法アプローチ1：線形探索（Linear Search）

最もシンプルな方法は線形探索です。配列を先頭（インデックス0）から末尾まで順番に走査し、「1」が最初に見つかった時点でそのインデックスを返します。もし配列内に「1」が存在しない場合は -1 を返します。

実装例

#include <iostream>
using namespace std;

int find1stOneInArray(int bin[], int n) {
    for (int i = 0; i < n; i++)
        if (bin[i] == 1)
            return i;
    return -1;
}

int main() {
    int bin[] = { 0, 0, 0, 1, 1, 1 };
    int n = sizeof(bin) / sizeof(bin[0]);
    cout << "配列内で最初に1が出現するインデックスは "
         << find1stOneInArray(bin, n);
    return 0;
}

出力結果

配列内で最初に1が出現するインデックスは 3

この方法の計算量は O(n) です。配列がソートされていることを活かしていないため、より効率的な手法が望まれます。

解法アプローチ2：二分探索（Binary Search）

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

探索の考え方は以下の通りです。

• 中央の要素が「1」であり、かつその直前の要素が「0」（または先頭要素）であれば、それが最初の「1」なのでインデックスを返す。
• 中央の要素が「1」だが条件を満たさない場合、答えは左側にあるので探索範囲を左半分に絞る。
• 中央の要素が「0」の場合、答えは右側にあるので探索範囲を右半分に絞る。

実装例

#include <iostream>
using namespace std;

int find1stOneInArray(int bin[], int n) {
    int low = 0;
    int high = n - 1;
    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 n = sizeof(bin) / sizeof(bin[0]);
    cout << "配列内で最初に1が出現するインデックスは "
         << find1stOneInArray(bin, n);
    return 0;
}

出力結果

配列内で最初に1が出現するインデックスは 3

まとめ

配列がソートされているという前提条件があるため、実務上は二分探索を採用するのがベストプラクティスです。特に配列サイズが大きい場合、二分探索によるパフォーマンス向上は顕著になります。