PHP二分查找算法

二分查找算法使用前提是查找的数组必须是一个有序的元素数组

下面一个demo,表示如果要查找的元素包含在有序数组中,二分查找返回其索引位置

<?php 
// 设置内存使用
ini_set('memory_limit','5120M');
// 生成有序数组,供测试使用
$arr = range(1,111111119);
// 测试例子
echo getPos($arr,1,111111119),PHP_EOL;
/**
 * 二分查找获取元素位置
 * @param  array $arr 查找数组
 * @param  int $item 查找的元素
 * @return int 查找的元素索引
 */
function getPos($arr,$item)
{
    $low = 0;
    $high = count($arr) - 1;
    while ($low <= $high) {
        $cen = (int)(($low + $high)/2);
        if($item == $arr[$cen]){
            return $cen;
        }elseif ($item < $arr[$cen]) {
            $high = $cen - 1;
        }elseif ($item > $arr[$cen]) {
            $low = $cen + 1;
        }
    }
    return 'Not Found!';
}

在终端执行,测试执行效率

time php index.php