-3

给定一个移位数组(例如):

[17 34 190 1 4]

哪个从(我们不知道原来的)

[1 4 17 34 190]

找到该数字的位置的好功能是什么?

例如,如果我通过 1,它将返回第 3 位。

4

2 回答 2

1

线性搜索答案总是有效的,但我相信你可以在 O(log) 时间内到达那里。

通过检查移位排序数组的值是否与假定的值相反,对移位点进行某种二进制搜索。就像创建一个 trie 一样。继续形成排序树,直到找到“非法”节点(伙计,这掩盖了很多细节——我知道)。这告诉您拐点在哪里,您现在将数组视为 2 个排序向量。快速检查要查找的值是否大于每个的最大条目,以便我们知道要搜索的向量。B在排序后的向量中搜索您的值并返回其索引。

困难的部分是找到拐点。:)

于 2013-02-14T19:03:50.570 回答
0

您将不得不扫描阵列。

size_t pos_in_arr(int *arr, size_t arr_size, int match)
{
    size_t i;
    for (i = 0; i < arr_size; i++)
        if (arr[i] == match)
            break;
    return i;
}

此函数将返回所要求的位置,或者在未找到元素的情况下返回比最大位置多一个。

解决方案是您所要求的,但它可能不是您需要的,因为它不会以任何方式使用数组已移动的事实。我怀疑原来的问题更复杂。

例如,如果您知道原始数组中的第一个元素是第五个,现在是第七个,而您要查找的元素是二十三,您可以回答“二十五”而无需实际扫描数组直到二十五位置,这可能是整个练习的重点。但要构建这样一个解决方案,需要更多地了解这个问题。

于 2013-02-14T19:02:49.853 回答