AIZU ALDS1_4_B 二分探索(精選18）

問題

数列Tに含まれる要素の中で数列Sに含まれる要素の個数を出力する問題です。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja

考察

基本通りの二分探索で実装しあっさりACしました。

#include <bits/stdc++.h>
using namespace std;

int binary_search(vector<int> num_list, int key){
  int left = 0;
  int right = num_list.size();
  while(right > left){
    int mid = (left + right)/2;
    if(num_list[mid] == key){
      return 1;
    }
    if(num_list[mid] > key){
      right = mid;
    }
    else if(num_list[mid] < key){
      left = mid + 1;
    }
  }
  return 0;
}

int main(){
  int n;
  cin>>n;
  vector<int>S(n);
  for(int i=0;i<n;i++){
    cin>>S[i];
  }
  int q;
  cin>>q;
  vector<int>T(q);
  for(int i=0;i<q;i++){
    cin>>T[i];
  }
  int ans=0;
  for(auto i:T){
    ans+=binary_search(S, i);
  }
  cout<<ans<<endl;
  return 0;
}