競技プログラミングでたびたび利用する二分探索について考察してみます。いっても、とくに競技プログラミングに限らず活用できると思います。リストに挿入するときのインデックス」を求めてみます。メソッドとして実装できます。メソッドのように「値が一致するインデックスを求める。メソッドのように書けます。リスト内の値は重複してもかまいません。例外処理は除いています。上記のメソッドは、リストのみ、しかも昇順にソート済みという制約の下で適用することができます。そこで、さらに汎用的に使えるように、抽象度を上げてライブラリを作ることを考えます。二分探索により実現できることは、見方を変えると「状態が変化する境界を見つけること」、厳密には「与えられた条件に対し、ある境界が存在して、その前方と後方で真偽が逆転する場合にその境界を見つけること」だと考えます。メソッドのようになります。この形にすれば、降順のリストにも、リスト以外の数値の範囲にも適用できます。(コメントは省略)、価格が所持金以下となる最後の整数を求めればよいです。次に小数向けのメソッドを用意して、二分法で平方根を求めてみます。誤差を表す桁数を指定できるようにしています。今回作成したライブラリを使って実装ができます。(GitHub)その他これまでは二分探索を実装するときに再帰を使っていたのですが、おそらく過去に読んだ解説に再帰を使うものが多かったためだと思います。使うようになりました。メソッドでは、重複する値を検索する場合、その最初のインデックスが返ってくるとは限りません。いうものを今年の8月に始めて、3~4か月をかけて水色に到達しました。スピード勝負は得意ではないのですが、難しめの問題を少し時間をかけて解くのが向いているようです。部門があるとしたらだいたい優勝していると思います。(スペースを切り詰めたりはしません。既定のフォーマットをしてから提出しています。別解が多くあり考察を楽しめる問題セットでした。解説してみたいと思います。円となるときの税抜価格はいくらか。全探索でも正解できます。使って次のように書けます。対する税抜価格はたかだか1個存在することがわかります。