【C++】配列をサイズKのセグメントに分割し、すべてのセグメントにキーXが存在するか判定する方法

概要

要素数 N の配列 arr1[]、検索対象のキー X、およびセグメントサイズ K が与えられたとき、「配列をサイズ K ごとの区間(セグメント)に区切った場合に、そのすべてのセグメントにキー X が含まれているか」を判定するのが本記事の課題です。

入力例1

arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4}
X = 4
K = 3

出力

Yes

この配列は、サイズ 3 の重なり合わないセグメントが 4 つ、すなわち {4, 6, 3}、{5, 10, 4}、{2, 8, 4}、{12, 13, 4} に分けられます。いずれのセグメントにも 4 が含まれているため、答えは「Yes」となります。

入力例2

arr1[] = { 22, 24, 57, 66, 35, 55, 77, 33, 24, 46, 22, 24, 26}
X = 24
K = 5

出力

Yes

{22, 24, 57, 66, 35}、{55, 77, 33, 24, 46}、{22, 24, 26} の 3 つのセグメントすべてに 24 が含まれているため「Yes」です。

入力例3

arr1[] = { 6, 9, 8, 13, 15, 4, 10}
X = 9
K = 2

出力

No

{6, 9}、{8, 13}、{15, 4}、{10} のうち、{8, 13} に 9 が含まれていないため「No」となります。

アルゴリズムの考え方

アプローチは非常にシンプルです。先頭からサイズ K ずつのセグメントを順に走査し、それぞれのウィンドウ内にキー X が存在するかどうかを確認します。

ポイントは、配列の長さ N が必ずしも K の倍数とは限らないことです。N を K で割り切れない場合、末尾に K より短い「端数のセグメント」が残るため、その最後のセグメントも忘れずにチェックする必要があります。

処理の流れを整理すると次のとおりです。

1. インデックス 0 から K 間隔でループを回し、各セグメント内で X を線形探索します。
2. あるセグメント内で X が 1 つも見つからなければ、即座に false を返します。
3. すべての完全なセグメントで X が見つかったら、N が K の倍数かどうかを確認します。
4. 倍数であれば true を返し、そうでなければ残りの端数部分(最後のセグメント)に対しても同様に探索を行います。

C++での実装例

以下が上記アプローチの実装です。

// C++コード:配列の各セグメント(サイズK)に
// 検索キー x が含まれるかどうかを判定する
#include <bits/stdc++.h>
using namespace std;
bool findxinkindowSize1(int arr1[], int X, int K, int N){
   int i;
   for (i = 0; i < N; i = i + K) {
      // インデックス i から始まるセグメント内で X を探索
      int j;
      for (j = 0; j < K; j++)
         if (arr1[i + j] == X)
            break;
      // ループが途中で抜けなかった場合(Xが見つからなかった場合)
      if (j == K)
         return false;
   }
   // N が K の倍数の場合
   if (i == N)
      return true;
   // N が K の倍数でない場合、最後の端数セグメントを確認
   int j;
   for (j=i-K; j<N; j++)
      if (arr1[j] == X)
         break;
   if (j == N)
      return false;
   return true;
}
// main関数
int main(){
   int arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4 };
   int X = 4, K = 3;
   int N = sizeof(arr1) / sizeof(arr1[0]);
   if (findxinkindowSize1(arr1, X, K, N))
      cout << "Yes" << endl;
   else
      cout << "No" << endl;
   return 0;
}

出力結果

Yes

計算量について

このアルゴリズムでは、配列の各要素を高々 1 回ずつ調べるため、時間計算量は O(N) となります。また、追加のメモリをほとんど使用しないため、空間計算量は O(1) です。配列全体を 1 回の走査で判定できる、非常に効率的な手法といえます。

まとめ

配列をサイズ K のセグメントに区切り、各セグメントにキー X が含まれるかを判定する問題は、単純な二重ループによる線形探索で解決できます。実装上の注意点は「N が K の割り切れない場合の末尾セグメントの扱い」であり、これを正しく処理することで境界条件のバグを防げます。計算量 O(N)・空間 O(1) と効率的なので、実務でもそのまま活用できるパターンです。