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

この問題では、0と1のみで構成されるバイナリ配列 bin[] が与えられ、その中に含まれる0の個数を求めることが課題となります。

配列はソート済みであり、すべての1が先頭に、すべての0が後ろにまとめて配置されています。つまり、最初の0が現れる位置が分かれば、残りの要素はすべて0であるため、簡単に個数を計算できます。

問題の例

入力:

arr[] = {1, 1, 1, 0, 0, 0, 0}

出力:

4

この例では、配列の後半に0が4つ連続しているため、答えは「4」となります。

解決アプローチ

この問題を解く鍵となるのは「配列がソート済みである」という性質です。配列内で最初に0が出現するインデックスを見つければ、0の総数は「配列の長さ − 最初の0のインデックス」で求められます。

最初の0を探す方法として、主に以下の2つの探索アルゴリズムが考えられます。

方法1: 線形探索（Linear Search）

線形探索では、配列を先頭から順に走査し、最初に0が現れた位置を返します。その位置と配列のサイズから0の個数を計算します。

この方法の計算量は O(N) です。最悪の場合、配列全体を走査する必要があるためです。

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

#include <iostream>
using namespace std;

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

int countZerosArr(int arr[], int n){
    int firstOccZero = findFirstZero(arr, n);
    if (firstOccZero == -1)
        return 0;
    return (n - firstOccZero);
}

int main(){
    int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The count of zeros in array is " << countZerosArr(arr, n);
    return 0;
}

出力:

The count of zeros in array is 5

方法2: 二分探索（Binary Search）

二分探索を使うと、より効率的に最初の0を見つけられます。配列の中央要素（mid）が1か0かを判定しながら探索範囲を半分ずつ絞り込んでいくことで、最初の0が出現するインデックスを特定します。

具体的には、次の手順で探索を行います。

• 中央の要素が0で、かつ直前の要素が1（または先頭要素）であれば、それが最初の0です。
• 中央の要素が1であれば、0は右側にあるため右半分を探索します。
• 中央の要素が0であっても直前が0であれば、さらに左側を探索します。

この方法の計算量は O(log N) となり、大規模な配列に対して非常に効率的です。

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

#include <iostream>
using namespace std;

int findFirstZero(int arr[], int start, int end){
    if (end >= start){
        int mid = start + (end - start) / 2;
        if ((mid == 0 || arr[mid - 1] == 1) && arr[mid] == 0)
            return mid;
        if (arr[mid] == 1)
            return findFirstZero(arr, (mid + 1), end);
        else
            return findFirstZero(arr, start, (mid - 1));
    }
    return -1;
}

int countZerosArr(int arr[], int n){
    int firstOccZero = findFirstZero(arr, 0, n - 1);
    if (firstOccZero == -1)
        return 0;
    return (n - firstOccZero);
}

int main(){
    int arr[] = {1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The count of zeros in array is " << countZerosArr(arr, n);
    return 0;
}

出力:

The count of zeros in array is 7

まとめ

ソート済みバイナリ配列内の0の個数を数える問題では、「最初の0の位置」に着目することが重要です。線形探索ではO(N)、二分探索ではO(log N)の計算量で解くことができ、特に二分探索は配列のソート済みという性質を活かした効率的なアプローチといえます。実務や競技プログラミングにおいても、データの特性を理解して適切なアルゴリズムを選択することが性能向上のポイントになります。