二分探索 (木じゃなくて)
線形探索と二分探索
探索問題において、"普通"の探し方が先頭から末尾まで一つずつ見ていくのが、線形探索
ソート済みの未探索の要素の真ん中を調べ、その値で探索済み未探索を分ける。これを繰り返すのが二分探索
atcoderでTLE
pythonで競技プログラミングをするとタイムアウト(TLE)することがよくあるが、abc146のC問題を何も考えずに解いていたら、TLEになってしまった。
コードの一部
手持ちのお金で変える最大を求める問題で、 言い換えると条件式に当てはまる最大を求める問題だった。
a,b,x = map(int,input().split()) def can_buy(arg): p = a * arg + b * len(str(arg)) return p <= x # true or false done = 0 uncheck = 10 ** 9 + 1 while uncheck - done > 1: p = (uncheck+done) // 2 if can_buy(p): done = p else: uncheck = p print(done)
要点
二分探索をする際は、以下の要素で書けばいい
- 条件判定する関数を作成
- 絞り込むための0から増加する変数と最大から減少する変数を定義
- 探索する範囲を割る2して、徐々に狭めるために、判定するたびに上記変数を更新
- whileで3を繰り返す