５．２ 線形検索（番兵版）

番兵の説明があったのでそのまま入れてみます。

#include <iostream>
#include <array>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i]; 
  }
}

static int linearSearch(int A[], int sentinel) {
  int i = 0;
  for (; A[i] != sentinel; i++);
  return i;
}

int main() {
  array<int, 10000 + 1> N;
  array<int, 500> Q;
  int s, t;

  cin >> s;
  inputArray(&N[0], s);

  cin >> t;
  inputArray(&Q[0], t);

  int found = 0;
  for (int i = 0; i < t; i++) {
    // set a sentinel
    N[s] = Q[i];
    if (linearSearch(&N[0], Q[i]) != s) {
      found++; 
    }
  }
  cout << found << endl;  

  return 0;
}

判定が減って効率的とのことですが、実測してないのでどこまで速いのかはようわかりません。