誤差のない小数二分探索(二分法)

前言

• https://twitter.com/codera_iroha/status/729675348615389185
• の続きが未だにない状況で、
• https://twitter.com/tanakh/status/781136467846234112
• を見つけてしまったので、書くことにしました。

背景

• 競技プログラミングでは二分探索は割と出てきますが、小数だとどこで探索を打ち切るかが問題になります。
• 現状、使われている主流な方法は、
  • EPSを用いる
  • 二分探索の回数を決める
• 方法になりますが、誤差が問題となります。

方法

• ここで、IEEE浮動小数点数は符号付き整数とみなしても大小関係が保たれることを利用します。
• つまり、double型をlong long型と解釈し、整数の二分探索を適用すればよいのです。
  • checkerにはlong long型をdouble型に変換した値を渡す。
• ただし、負の数の扱いは異なるため、正の数を経由して型変換する必要があります。

実装

• RubyのRange#bsearch
  • 本家 https://github.com/ruby/ruby/blob/trunk/range.c
  • backports https://github.com/marcandre/backports/blob/master/lib/backports/2.0.0/range/bsearch.rb
• backports版を 私が適当にC++に移植したもの
  • https://github.com/cielavenir/cpp_libraries/tree/master/binarysearch
  • 本家の実装を今更見ましたが、reinterpret_castではなくunionを使っているようです。この方が良かったかも。