xyzshop/helper/algorithm_helper.php

<?php

/**
 * Created by PhpStorm.
 * User: stanley-king
 * Date: 16/6/24
 * Time: 上午1:18
 */
class algorithm_helper
{
//    static public function bsearch($needle, $haystack)
//    {
//        $high = count($haystack);
//        $low = 0;
//
//        while ($high - $low >= 1){
//            $probe = ($high + $low) / 2;
//            if ($haystack[$probe] < $needle){
//                $low = $probe;
//            }else{
//                $high = $probe;
//            }
//        }
//
//        if ($high == count($haystack) || $haystack[$high] != $needle) {
//            return false;
//        }else {
//            return $high;
//        }
//    }

    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;
    }
}