C++で2つの配列の要素を比較してカウントする方法：二分探索による効率的なアプローチ

ここでは、ソートされていない2つの配列 arr1[] と arr2[] が与えられた場合を考えます。目的は、arr1[] の各要素について、「その要素以下の値が arr2[] 内にいくつ存在するか」を数えることです。なお、両方の配列には重複した要素が含まれている可能性がある点に注意してください。

入出力例

入力：

N = 6
M = 7
arr1[N] = {1, 2, 5, 0, 6, 3}
arr2[M] = {0,0,1,2,1,3,4,6,8}

出力：

4 5 7 2 8 6

この問題を解くためのアプローチ

arr1[] の各要素について、それ以下の要素が arr2[] にいくつあるかを調べるには、まず arr2[] をソートし、その上で二分探索（バイナリサーチ）を活用するのが効果的です。これにより、各要素に対する探索を高速に行うことができます。

• arr1 と arr2 のサイズをそれぞれ「m」「n」として入力を受け取ります。

• 配列の要素を入力します。

• 関数 countInSecond(int *arr1, int *arr2, int m, int n) は、2つの配列とそのサイズを引数として受け取り、条件を満たす要素の個数を出力します。

• まず arr2[] をソートします。

• arr1[] を順に走査しながら、二分探索を用いて arr2[] 内で「その要素以下」の境界位置を特定します。

• 見つかった境界位置から、条件を満たす要素の個数を算出して返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
void countInSecond(int *nums1,int *nums2,int m,int n){
   sort(nums2, nums2+n);
   int i=0;
   for(int i=0;i<m;i++){
      int s=0;
      int e=n-1;
      while(s<=e){
         int mid= (s+e)/2;
         if(nums2[mid]<=nums1[i])
            s= mid+1;
         else
            e= mid-1;
      }
      cout<<e+1<<" ";
   }
}
int main(){
   int m=6;
   int n=9;
   int arr1[m]={1,2,5,0,6,3};
   int arr2[n]= {0,0,1,2,1,3,4,6,8};
   countInSecond(arr1,arr2,m,n);
   return 0;
}

実行結果

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

4 5 7 2 8 6

この結果は、arr1 の各要素（1, 2, 5, 0, 6, 3）について、それぞれ arr2 内にある「その要素以下」の値の個数を表しています。つまり、arr1 のすべての要素に対するカウント結果が {4 5 7 2 8 6} となります。