PHP – Binary Search
     发布在:PHP      浏览:36      评论:0 条评论

问题描述

用 PHP 实现二分查找

要求:返回不大于所查询元素的最后一个元素的下标

给定:$A = [1, 3, 5, 8, 13, 19, 20, 31, 43, 50];

查询 8,结果返回:3
查询 0,结果返回:-1
查询 100,结果返回:9

代码实现

该算法详解请看:《C++ 数据结构(二)向量(5)二分查找》

<?php
function binSearch(array $A, int $e, int $lo, int $hi)
{
    while ($lo < $hi) {

        $mi = ($lo + $hi) >> 1; // 折半

        ($e < $A[$mi]) ? $hi = $mi : $lo = $mi + 1; // [$lo, $mi) or ($mi, $hi)

    }

    return --$lo;
}

$A = [1, 3, 5, 8, 13, 19, 20, 31, 43, 50];

if ($argc > 1) echo binSearch($A, $argv[1], 0, count($A));

PHP - Binary Search

Responses