7K12 blog

猫でも分かるアルゴリズム解説

AOJ ALDS1_4_B Binary Search

f:id:tkr987:20200708024810p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4632584

  • lower_boundとupper_boundを比較することで値が存在するか分かる
  • lower_bound(x) == upper_bound(x) 値xが存在しない
  • lower_bound(x) != upper_bound(x) 値xが存在する

f:id:tkr987:20200708024954p:plain

制約から O(N^2)はTLEするので二分探索して計算量を減らす。STLにはlower_boundとupper_boundという2種類の二分探索が用意されており、これらを組み合わせるとシンプルに存在するかどうか判定できる。計算量は O(q \log n)