エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
競プロ用二分探索まとめ - Qiita
いつ使うのか N個の要素に対して繰り返し大小判定をし、 条件を満たす最大/最小の値を求めるとき。 条件... いつ使うのか N個の要素に対して繰り返し大小判定をし、 条件を満たす最大/最小の値を求めるとき。 条件を満たす要素を数え上げるとき。 ソートしたリストのK番目を求めるとき。(リストのK番目の数字以下の数字の個数<=Kを満たす最大の値) 何がいいのか 通常、一個一個見ていくとO(N)のオーダーがかかるところをO(logN)に短縮することができる。 どうするのか 予めN個の要素をソートしておく。 ソートした全要素の両端より外側の値を2つ選ぶ。(=初期値を両端としてしまうとその点は評価されないため全てTrue/Falseだった場合に不正になる) 次の操作を繰り返し、最終的には条件を満たすokと満たさないngの境界を求める。 2値の平均値(中点)が条件を満たすか判定し、満たすならokをその中点の値とする。満たさないならngを中点とする。 okとngの絶対値の差が1未満になったら繰り返しを終了する。