xyzshop/helper/algorithm.php

<?php

/**
 * Created by PhpStorm.
 * User: stanley-king
 * Date: 16/6/24
 * Time: 上午1:18
 */
function less($x,$y)
{
    return $x < $y;
}

class algorithm
{
    static function bsearch($x, $list)
    {
        $left = 0;
        $right = count($list)-1;

        while ($left <= $right) {
            $mid = ($left + $right) >> 1;

            if ($list[$mid] == $x) {
                return $mid;
            } elseif ($list[$mid] > $x) {
                $right = $mid - 1;
            } elseif ($list[$mid] < $x) {
                $left = $mid + 1;
            }
        }

        return -1;
    }

    static function binary_search($sortarr, $val, $compare = "less")
    {
        $last = count($sortarr);
        $first = self::lower_bonud($sortarr,$val,$compare);
        return $first != $last && !$compare($val, $sortarr[$first]);
    }

    //返回位置标记了一个 >= value 的值。
    static function lower_bonud($container, $val,$compare = "less")
    {
        if(!is_array($container)) {
            return -1;
        }

        $len = count($container);
        $first = 0;
        while ($len != 0)
        {
            $l2 = intval($len / 2);
            $m = $first + $l2;
            if ($compare($container[$m],$val))
            {
                $first = ++$m;
                $len -= $l2 + 1;
            }
            else {
                $len = $l2;
            }
        }
        return $first;

    }

    //返回位置标记了一个 > value 的值。
    static function upper_bound($container, $val,$compare = "less")
    {
        if (!is_array($container)) {
            return -1;
        }

        $len = count($container);
        $first = 0;
        while ($len != 0)
        {
            $l2 = intval($len / 2);
            $m = $first + $l2;
            if ($compare($val,$container[$m])) {
                $len = $l2;
            } else {
                $first = ++$m;
                $len -= $l2 + 1;
            }
        }

        return $first;
    }

    static function array_insert(&$arr,$pos,$val)
    {
        array_splice($arr,$pos,0,$val);
    }
    static function array_erase(&$arr,$pos)
    {
        return array_splice($arr,$pos,1);
    }
}