c - C中的数组问题

Question

给定一个移位数组（例如）：

[17 34 190 1 4]

哪个从（我们不知道原来的）

[1 4 17 34 190]

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

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

Answer 1

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

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

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

Answer 2

您将不得不扫描阵列。

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

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

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

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