0

我有要存储的数字集合（任意顺序）。

伪代码：

id_a:[3,5,7,11]
id_x:[3,5,10,21]
id_b:[12,24,25,26]
etc.

我需要能够搜索所有集合并返回 group_ID。例如，如果我查找 5，我应该返回['id_a','id_x']. 我想通过某种映射有效地做到这一点，而不是通过循环遍历所有集合的所有数量。我还希望能够直接映射到每个键并取回集合（例如，'id_x'返回[3,5,10,21]）；再次，我更喜欢在不循环按键的情况下有效地完成此操作。

编辑： 我可以使用数字作为键并有效地取回'id_ '。或者，我可以采用另一种方式并使用 'id_ ' 作为键并有效地取回数字数组。但是，我希望能够在两个方向上高效地进行。我想我可以维护两个数组，但这看起来很乱。

4

1 回答 1

3

您的示例都按排序顺序显示数组值。如果它们总是按排序顺序排列，那么您可以使用二进制搜索来查找已知值。这段代码：

function binarySearch($needle, array $haystack) {
    $high = count($haystack) - 1;
    $low = 0;
    $mid = false;
    while ($high >= $low) {
        $mid = ($high + $low) >> 1;
        $t = $needle - $haystack[$mid];
        if ($t < 0) {
            $high = $mid - 1;
        } elseif ($t > 0) {
            $low = $mid + 1;
        } else {
            return $mid;
        }
    }

    return $mid;
}

function searchArrays($needle) {
    static $id_a = array(3,5,7,11);
    static $id_x = array(3,5,10,21);
    static $id_b = array(12,24,25,26);
    static $arrayNames = array('id_a', 'id_x', 'id_b');

    $rv = array();
    foreach ($arrayNames as $arrayName) {
        $array = $$arrayName;
        $index = binarySearch($needle, $array);
        if ($array[$index] == $needle) {
            $rv[] = $arrayName;
        }
    }

    return $rv;
}

$needles = range(3,8);
foreach ($needles as $needle) {
    $result = searchArrays($needle);
    printf("searchArrays(%s)=%s\n", $needle, join(', ', $result));
}

将输出以下内容：

searchArrays(3)=id_a, id_x
searchArrays(4)=
searchArrays(5)=id_a, id_x
searchArrays(6)=
searchArrays(7)=id_a
searchArrays(8)=
于 2012-09-01T15:46:13.787 回答