PHPルックアップアルゴリズム

静的検索

シーケンス検索

/**
* Common search
*
* @param  array  $arr
* @param  mixed  $item
*
* @return int
*/
public function search(array $arr, $item)
{
    for ($i = 0; $i < count($arr); $i++) {
        if ($arr[$i] == $item) {
            return $i;
        }
    }

    return -1;
}

折半検索

/**
* Binary search
*
* @param  array  $arr
* @param  mixed  $item
*
* @return int
*/
public function binSearch(array $arr, $item)
{
    if (empty($arr)) {
        return -1;
    }

    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        //$mid  = intval(($high + $low) / 2)     
        $mid  = intval(($high - $low) / 2) + $low;
        $val = $arr[$mid];

        if($item == $arr) {
            return $mid;
        } elseif ($item < $val) {
            $high = $mid -1;
        } else {
            $low = $mid + 1;
        }
    }

    return -1;
}

再帰折半検索

/**
* Recursion search 
*
* @param  array $arr
* @param  mixed $item
* @param  int  $low
* @param  int  $high
*
* @return int 
*/

public function binRecSearch(array $arr, $item, $low, $high){
    if (empty($arr) || $low > $high || $low < 0) {
        return -1;
    }

    $low = 0;
    $high = count($arr) - 1;

    if ($low <= $high) {
        $mid = intval(($high - $low) / 2) + $low;
        if ($item == $arr[$mid]) {
            return $mid;
        } elseif ($item < $arr[$mid]) {
            return binRecSearch($arr, $item, $mid + 1, $high);
        } else {
            return binRecSearch($arr, $item, $low, $mid - 1);
        }
    }

    return -1;
}