0と1のみで構成されたソート済み配列の遷移点をC++で効率的に求める方法

0と1のみで構成されたソート済みの数値配列が与えられたとき、遷移点(トランジションポイント)を見つける問題を考えます。遷移点とは、配列内で最初に「1」が出現するインデックスのことです。

入力例1

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

出力:

4

説明: 0と1で構成されたこの配列では、インデックス「4」の要素が最初の「1」になっているため、答えは4となります。

入力例2

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

出力:

2

説明: この配列では、インデックス「2」の要素が最初の「1」であるため、2を返します。

この問題の解き方

与えられた整数配列の中から、最初に「1」が出現するインデックスを見つける必要があります。配列はすでにソートされているため、二分探索法(バイナリサーチ)を使えば、線形探索よりも高速にO(log N)の計算量で解くことができます。

• N個の2進数(0と1)からなる配列を入力として受け取ります。
• 関数 transitionPoint(int *arr, int n) は、配列とそのサイズを引数に取り、最初の「1」が出現するインデックスを返します。
• 2つのポインタ low と high を用意し、それぞれ「0」と「n-1」で初期化します。
• 配列の中央(mid)の要素を調べ、「1」であるかどうかを確認します。
• 中央の要素が「1」の場合、それが最初の「1」かどうか(直前の要素が「0」または先頭であるか)を確認し、条件を満たせばそのインデックスを返します。そうでなければ、探索範囲を左半分に狭めて続行します。
• 中央の要素が「0」の場合は、探索範囲を右半分に移動させます。
• low が high を超えるまでこの手順を繰り返します。「1」が見つからない場合は -1 を返します。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int transitionPoint(int *arr, int n){
    int low=0;
    int high= n-1;
    while(low<=high){
        int mid = (low+high)/2;
        if(arr[mid]==0)
            low= mid+1;
        else if(arr[mid]==1){
            if(mid==0 || (mid>0 && arr[mid-1]==0))
                return mid;
            high= mid-1;
        }
    }
    return -1;
}
int main(){
    int n= 6;
    int arr[n]= {0,0,0,1,1,1};
    int ans= transitionPoint(arr,n);
    if(ans>=0){
        cout<<"Transition Point is:"<<ans<<endl;
    }
    else{
        cout<<"Not Found"<<endl;
    }
    return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

Transition Point is: 3

配列 {0,0,0,1,1,1} の場合、「1」はインデックス「3」に初めて出現するため、出力は「3」となります。なお、配列に「1」が一切含まれていない場合は、関数が -1 を返し、「Not Found」と表示されます。