lower_bound と upper_bound

• 挙動

  • lower_bound: xs[i] ≥ key となる最小の i を求める
  • upper_bound: xs[i] > key となる最小の i を求める
  • (そういう i が存在しない場合は xs[i].len() を返す)

• 解釈

  [1, 3, 5, 5, 6, 7]
         [----)
         L    U
  
  

  lower_bound で混乱している人かわいそう - えびちゃんの日記

  key と同じ値が [lower_bound, upper_bound) の範囲にある

• 配列上の切り捨てと切り上げ

  

二分探索の簡単な応用例

条件を満たす範囲の大きさを求める

条件を満たすギリギリの値を求める

• ABC362 G - Count Substring Query

  • 条件を満たす suffix の範囲を二分探索2回で求める

• 2つの数列A, B が与えられたとき

  • A[i] + B[j] <= S となる (i, j) の個数
  • A[j] + B[j] <= S となる最小の A[j] + B[j] の値

  など

  B をソート後、A全探索→B二分探索

  半分全列挙後に使うこともある。

  参考半分全列挙による全探索の高速化 | アルゴリズムロジック

最大化・最小化

• ABC319 D - Minimum Width
  • 文章がM行に収まるときのウィンドウの幅の最小値
• ABC023 D - 射撃王（最大値の最小化）
  • 問題: 風船の初期の高さと上に移動する速さが与えられる。1秒ごとに風船を割る。
  • 風船が割られたときの高さの最大値を最小化する。
  • 「高さの最大値をx以下にできるか」で二分探索する
    • 4以下にはできない、5以下にはできない、6以下にはできる→最小値は6とわかる。
  • 高さの最大値をx以下にすると決めたら、風船を割るまでの時間が決まる
• Q2-8. ひもを切る | アルゴ式
  • N本の紐から同じ長さの紐をK本作りたい。その紐の長さの最大値は？

k番目の数を求める