いわゆるバイナリサーチですね。知識で知っているのと自分で書くのとは大違いで大変です。
#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 binarySearch(int S[], int n, int T[], int q) { int found = 0; for (int i = 0; i < q; i++) { int left = 0; int right = n; while (left < right) { int mid = (left + right) / 2; if (T[i] == S[mid]) { found++; left = right; } else if (T[i] < S[mid]) { left = left; right = mid; } else { left = mid + 1; right = right; } } } return found; } int main() { int n, q; array<int, 100000> S; array<int, 50000> T; cin >> n; inputArray(S.data(), n); cin >> q; inputArray(T.data(), q); int found = binarySearch(S.data(), n, T.data(), q) ; cout << found << endl; return 0; }
解説のコードではサーチ部分を関数化してました。そちらのほうが見やすいので清書。
#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 bool binarySearch(int S[], int n, int search) { int left = 0; int right = n; int mid = 0; while (left < right) { mid = (left + right) / 2; if (search == S[mid]) { return true; } else if (search < S[mid]) { left = left; right = mid; } else { left = mid + 1; right = right; } } return false; } int main() { int n, q; array<int, 100000> S; array<int, 50000> T; cin >> n; inputArray(S.data(), n); cin >> q; inputArray(T.data(), q); int found = 0; for (int i = 0; i < q; i++) { if (binarySearch(S.data(), n, T[i])) { found++; } } cout << found << endl; return 0; }