C++でソート済みバイナリ配列に含まれる「1」の個数を数える方法

このチュートリアルでは、ソート済みバイナリ配列の中から「1」の個数を求めるプログラムについて解説します。

扱うデータは、0と1のみで構成された配列です。課題は、この配列内に存在する「1」の個数を効率的に数えることです。

アプローチのポイント

配列が「1」が先頭側、「0」が末尾側という順序でソートされている場合、先頭から順に走査する線形探索では O(n) の時間がかかります。しかし、二分探索を活用すれば、O(log n) の時間計算量で「1」と「0」の境界位置を見つけられます。

アルゴリズムの流れは以下のとおりです。

• 探索範囲の中央要素 mid を確認する
• arr[mid] が 1 であり、かつ arr[mid+1] が 0（または mid が配列末尾）であれば、mid + 1 が「1」の個数となる
• arr[mid] が 1 であれば、右半分を再帰的に探索する
• arr[mid] が 0 であれば、左半分を再帰的に探索する

実装例

#include <bits/stdc++.h>
using namespace std;

// 「1」の個数を返す関数
int countOnes(bool arr[], int low, int high){
    if (high >= low){
        int mid = low + (high - low)/2;
        // mid が「1」ブロックの最後尾かどうかを判定
        if ( (mid == high || arr[mid+1] == 0) && (arr[mid] == 1))
            return mid+1;
        if (arr[mid] == 1)
            return countOnes(arr, (mid + 1), high);
        return countOnes(arr, low, (mid -1));
    }
    return 0;
}

int main(){
    bool arr[] = {1, 1, 1, 1, 0, 0, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Count of 1's in given array is " << countOnes(arr, 0, n-1);
    return 0;
}

出力結果

Count of 1's in given array is 4

まとめ

このコードでは、サンプル配列 {1, 1, 1, 1, 0, 0, 0} に対して「1」が4個含まれていることが正しく検出されています。二分探索を用いることで、要素数が非常に大きい配列でも高速に処理できる点が大きなメリットです。なお、配列が昇順（0が先、1が後）にソートされている場合は、判定条件を反転させるだけで同じ考え方を応用できます。