arrays - 在未知长度的数组中查找 x 的位置

Question

给定一个无限数组（未知数组长度），并且在这个无限数组中有 n 个整数元素。n（已排序元素的数量）是未知的。在 log n 时间内找到整数 i 在这个无限数组中的位置。

Answer 1

log n 表示一直将数组除以 2，直到找到它，就像在二进制搜索中一样……所以你需要知道 n 的值。

C#代码：

调用函数的代码：

int position = findInteger(array, 0, searchedValue);

功能：

public int findInteger(int[] array, int position, int searchValue)
{
    if(array[position] = searchValue)
        return position;
    else if (array[position] > searchValue)
        position = position / 2;
    else // array[position] < searchValue
        position = (array.Count() + position)/2;
    findInteger(array, position, searchValue);
}

Answer 2

从问题陈述来看，似乎存在一个长度不定的数组 A，其中至少存在 n 个条目并按排序顺序排列。我们将假设前 n 个条目是按升序排列的正整数，并且如果 j >= n 则访问 A[j] 返回 nil。一开始，n 是未知的。给定 i，问题是确定 j 使得 A[j] == i（或者如果不j<n存在，则返回 nil）。

1. 设置 k=0，L=1。
2. 如果是真的，请执行第 3 步。
3. 设置 k = L 和 L = 2*L。如果 A[L] 为 nil，则进入第 4 步。如果 A[L] > i，则进入第 5 步。否则继续（在第 2 步的 while 循环中）。
4. 现在k < n < L。在 A[k:L] 中进行二进制搜索以找到最后一个非零条目 A[n-1]；设置 L=n-1; 然后转到第 5 步。
5. 现在 A[L] >= i。在 A[k:L] 中进行二分搜索以找到 i。如果找到则返回其索引，否则返回 nil。

要看到所述方法是 O(ln n) 有界的，请注意它最多使用2*lg(n)步骤来找到 n（或 L 使得 A[L] > i），然后最多lg(n)使用步骤在 A[k 中找到 i :L]，其中 lg(n) = ln(n)/ln(2)。

如果假设当 j >= n 时访问 A[j] 不会返回 nil，而是返回一个“随机数”，那么这种方法就失效了；一方面，它可能会找到 A[j] == i 但 j > n; 另一方面，O(ln n) 时间界限可能不成立，或者仅在概率上成立；该算法需要重新表述以检测 A[L] 值序列的减少；如果 A 满足 A[n+1] > A[n] > A[n-1]，那么无论如何都无法确定 n。