search 二分探索

二分探索

独自のクラスでも使えるようにテンプレート化した二分探索用クラスです。Verify済みです。
Feb. 2, 2020, 1:52 p.m.

目次

解説

二分探索用クラスです。

以下の実装を汎用的なターゲットに適用できるようにクラス化したものです。

https://qiita.com/drken/items/97e37dd6143e33a64c8c

Verify用の問題

https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_B

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <vector>

using namespace std;


/*
 * 汎用二分探索用クラス
 * 参考: https://qiita.com/drken/items/97e37dd6143e33a64c8c
 */
template<class T>
class BinarySearch {
public:
  vector<T> vec;

  BinarySearch(vector<T> &v) {
    vec = v;
  }

  /*
   * vec中からkeyを二分探索します.
   * 見つかった場合はkeyが出現する最小のインデックスを返します.
   * 見つからない場合はkeyを初めて超えたインデックスを返します.
   */
  int lower_bound(T key) {
      int ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
      int ok = (int)vec.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

      /* ok と ng のどちらが大きいかわからないことを考慮 */
      while (abs(ok - ng) > 1) {
          int mid = (ok + ng) / 2;

          if (isOK(mid, key)) ok = mid;
          else ng = mid;
      }
      return ok;
  }

  /*
   * keyがvec中に含まれるかどうかを返します.
   */
  bool include(T key) {
    int idx = lower_bound(key);
    if (idx >= vec.size()) return false;
    return vec.at(idx) == key;
  }

private:
  // index が条件を満たすかどうか
  bool isOK(int index, T key) {
      if (vec.at(index) >= key) return true;
      else return false;
  }
};

/*
 * Verify用問題
 * https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_B
 */

int N, Q;
vector<int> S, T;

int main() {
  // input
  cin >> N;
  int x;
  for (int i=0; i<N; i++) cin >> x, S.push_back(x);
  cin >> Q;
  for (int i=0; i<Q; i++) cin >> x, T.push_back(x);

  // solve
  int total = 0;
  auto bs = BinarySearch<int>(S);
  for (auto t: T) {
    total += bs.include(t);
  }
  cout << total << endl;
  return 0;
}