学生の備忘録なブログ

日々のことを忘れないためのブログです。一日一成果物も目標。技術系はQiitaにあげるように変更しました。

二分探索 (木じゃなくて)

線形探索と二分探索

探索問題において、"普通"の探し方が先頭から末尾まで一つずつ見ていくのが、線形探索

ソート済みの未探索の要素の真ん中を調べ、その値で探索済み未探索を分ける。これを繰り返すのが二分探索

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)

要点

二分探索をする際は、以下の要素で書けばいい

  1. 条件判定する関数を作成
  2. 絞り込むための0から増加する変数と最大から減少する変数を定義
  3. 探索する範囲を割る2して、徐々に狭めるために、判定するたびに上記変数を更新
  4. whileで3を繰り返す