二分探索サンプルコード集（コピペ用） - まめめも

二分探索は、感覚的なわかりやすさに反してバグが入りやすいことで有名なアルゴリズムです。20 の教科書のうち 15 でバグっていたという報告もあるそうです。 実際、自分も書くたびにバグに苦しんできました。変な値を返すだけでなく、out of bounds アクセスや無限ループもよく起きます。一旦動いたと思っても、後になってバグが発症することも多く、たちが悪いです。 そこで、きちんとテストした二分探索のサンプルコードを自分のコピペ用に作ってみました。 動作仕様 (境界探索版) ソートした配列 a に対して、「値が c 以上になる範囲のうちの一番左のインデックス」を返す関数 bsearch_min を書きます。 a = [0, 1, 1, 1, 2, 2, 2, 3] p bsearch_min(a, 2) #=> 4 値が c 以上になる値がない場合は a.size を返します。空配列の場合は