5.3 二分探索

いわゆるバイナリサーチですね。知識で知っているのと自分で書くのとは大違いで大変です。

#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;
}