2分探索 Binary Search : PHPで実装

Tweet

Pocket

2分探索をPHPで実装するサンプルです。
whileを使うサンプルと再帰を使うサンプルを掲載しています。

while版

<?php
/**
 * 2分探索
 *
 * @param integer[] $arr 探索対象 昇順の整数配列
 * @param integer   $v   探索値
 * @return boolean  $arrに$vがあればtrue,なければfalse
 */
function search($arr, $v)
{
    $result = false;
    while (true) {
        $len = count($arr);
        if ($len === 0) {
            break;
        }
        if ($len === 1) {
            if ($arr[0] === $v) {
                $result = true;
                break;
            }
            break;
        }
        if ($len === 2) {
            if ($arr[0] === $v) {
                $result = true;
                break;
            }
            if ($arr[1] === $v) {
                $result = true;
                break;
            }
            break;
        }
        /** @var integer $m */
        $m = (int) floor($len / 2);
        if ($arr[$m] === $v) {
            return true;
            break;
        }
        if ($v < $arr[$m]) {
            $arr = array_slice($arr, 0, $m);
        } else {
            $arr = array_slice($arr, $m);
        }
    }

    return $result;
}

再帰版

<?php
/**
 * 2分探索
 *
 * @param integer[] $arr 探索対象 昇順の整数配列
 * @param integer   $v   探索値
 * @return boolean  $arrに$vがあればtrue,なければfalse
 */
function search($arr, $v)
{
    $len = count($arr);
    if ($len === 0) {
        return false;
    }
    if ($len === 1) {
        return ( $arr[0] === $v ) ? true : false;
    }
    if ($len === 2) {
        if ($arr[0] === $v) {
            return true;
        } elseif ($arr[1] === $v) {
            return true;
        } else {
            return false;
        }
    }
    /** @var integer $m */
    $m = floor($len / 2);
    if ($arr[$m] === $v) {
        return true;
    }
    if ($v < $arr[$m]) {
        $arr  = array_slice($arr, 0, $m);
        $result = call_user_func_array('search', [$arr, $v]);
    } else {
        $arr  = array_slice($arr, $m);
        $result = call_user_func_array('search', [$arr, $v]);
    }

    return $result;
}