search.cc

#include <stdio.h>
#include <vector>
#include <iostream>
#include <cassert>

using namespace std;

bool serach(int x, vector<int> array)
{
  for (int i=0;i<array.size();i++) {
    if (array[i] == x) {
      return true;
    }
  }
  return false;
}






bool biserach(int x, vector<int> array)
{
  //printf("x=%d\n",x);
  int min = 0;
  int max = array.size();
  int mid = max  / 2;

  assert(min<=max);
  while(min<=max) {
    //printf("min=%d,max=%d,[%d]=%d\n",min,max,mid,array[mid]);
    if (array[mid] < x) {
      //printf("a\n");
      min = mid+1;
    }

    else if (array[mid] > x) {
      //printf("b\n");
      max = mid-1;
    }
    else {
      //printf("c\n");
      return true;
    }
    mid = ((max - min) / 2)+min;
  }
  assert(min>max);
  return false;
}



int main() 
{
  int n;
  vector<int> a1;
  cin >> n;
  for (int i=0;i<n;i++) {
    int x;
    cin >> x;
    a1.push_back(x);
  }
  int m;
  cin >> m;
  int cnt = 0;
  for (int i=0;i<m;i++) {
    int x;
    cin >> x;
    if (biserach(x,a1)) {
      cnt++;
    }
  }
  cout << cnt << endl;
  //cnt >> cout;
}