汎用バイナリサーチ（二分探索） in PHP #PHP

目的

初投稿です。よろしくお願いします。

内容は、二分探索自体の説明ではなく、一つの実装の話になります。

なぜPHPで二分探索のような、基本のアルゴリズムを自分で書く、みたいな記事を書くのか、という理由から説明すると、仕事ではWebエンジニアなので、アルゴリズムを自分でフルスクラッチする、ということはほとんどないのですが、最近ちょっとブームに乗って？Atcoderで競プロを初めてみて、何度も書くようなアルゴリズムが上手く整理できてなくて、これじゃダメだ！ということで、自分が使えるはずのアルゴリズムを整理していました。

その中で、二分探索、ソートの条件が変わった時とかに毎回既存のコードからちょこちょこいじるのなんとかならないかなー・・・と思っていたときに、海外のブログ記事で、汎用的なものをみつけて、これいいんじゃない？と思ったので、僕みたいな英語のサイトは毎回後回しにする人向けに記事にしてみようか、と思いました。

実装

前置きはここまでで、実装の話に移ります。
内部は普通の二分探索の実装ですが、大小関係を関数内で定義する代わりに、ユーザー定義の比較関数(フォーマットはusortと同じ）を引数に渡すことで、ソートされた配列のソート条件を設定できます。

<?php
/**
 * 汎用binary_search
 *
 * @param array $haystack ソートされた配列
 * @param $start_index - 検索対象の配列のfirst index
 * @param $end_index - 検索対象の配列のlast index
 * @param $needle - 検索したい値
 * @param callable $value_compare_func - ユーザー定義の比較関数
 * @return int　- 見つかったneedleのindex or  -(needleより大きい最小の要素のindex + 1)
 */
function binary_search(array $haystack, $start_index, $end_index, $needle, callable $value_compare_func)
{
    $low = $start_index;
    $hi = $end_index - 1;

    while ($low <= $hi) {
        $mid = (int)(($hi - $low) / 2) + $low;
        $compare = call_user_func($value_compare_func, $haystack[$mid], $needle);

        if ($compare < 0) {
            $low = $mid + 1;
        } elseif ($compare > 0) {
            $hi = $mid - 1;
        } else {
            return $mid;
        }
    }
    return -($low + 1);
}

使用例

宇宙船演算子の貴重なusageなので積極的に推していくスタイル。
PHP5.6などで使えない場合などは3項演算子などを使っても良いと思いますが、あるものは使いましょう。
下記の例は、ascとdescだけなので、この程度なら関数内で書いても良いですが、特殊なソート条件の時はより有効になると思います。

$asc = [2, 4, 6, 8, 10, 12, 14];

//存在する要素
$idx1 = binary_search($asc, 0, sizeof($asc), 6, function ($a, $b) {
    return ($a <=> $b);
});

//存在しない要素
$idx2 = binary_search($asc, 0, sizeof($asc), 5, function ($a, $b) {
    return ($a <=> $b);
});
echo $idx1 . "\n";  //2 →　asc[2]=6である。
echo $idx2 . "\n";  //-3 →　asc[2] が5より大きい最大の要素である。（0の時に区別できないので-1されている。）

$desc = [14, 12, 10, 8, 6, 4, 2];

$idx3 = binary_search($desc, 0, sizeof($desc), 6, function ($a, $b) {
    return -($a <=> $b);
});

echo $idx3 . "\n";  //4 →　desc[4]=6である。

参考

All purpose binary search in PHP
https://terenceyim.wordpress.com/2011/02/01/all-purpose-binary-search-in-php/

まとめ

比較関数を引数として渡すのと、見つからなかった時にnullとかではなく、境界値をちゃんと返却するのが実装のポイントになっていますね。
連想配列のキーに関するソートだったり、特殊な比較条件のソートだったり、目的の値自体が存在しなくても境界値とりたかったり、等の要件を満たせたりして、わりと便利なのではないでしょうか。
当たり前のことかもしれないですが、汎用的なモジュール(今回は関数一つですが）を作っておくと、他でベタに実装しているコードをコピペしてちょっと直せば使える！って感じで雑に中を書き換えて上手く動かない！ってことがなくなって便利ですね

PHPで競プロ(*´ω｀*)ﾊﾔﾙ？