c - 查找是否存在任何 i 以便 array[i] 等于 i 的算法

Question

我的 CS 教授给我布置了一个作业:

在 O(logn) 时间内查找，如果在给定的不同整数的预排序数组中有一个索引 i，则 array[i] = i。证明时间为O(logn)。

更新:整数可以是负数、0 或正数。

好吧，所以我在这方面遇到了一些困难。我的想法是这样的:

使用二分查找，如果array[mid] <= startindex，我们只能确定中间元素左边没有这个值，其中mid是中间元素的索引，startindex是数组的开始.

对应的数组右半边的规则是array[mid] >= startindex + numel，其中变量同上，numel是mid右边的元素个数。

这看起来不像 O(logn)，因为在最坏的情况下我必须遍历整个事情，对吧？有人可以在这里提示我正确的方向，或者告诉我这行得通吗？

关于如何正式证明这一点的任何想法？我不是在要求一个明确的答案，更多的是一些帮助让我理解。

在 C 中:

int _solve_prob_int(int depth, int start, int count, int input[])
    {
    if(count == 0)
        return 0;
    int mid = start + ((count - 1) / 2);
    if(input[mid] == mid)
        return 1;

    if(input[mid] <= start && input[mid] >= start + count)
        return 0;

    int n_sub_elleft = (int)(count - 1) / 2;
    int n_sub_elright = (int)(count) / 2;

    if(input[mid] <= start)
        return _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input);

    if(input[mid] >= start + count)
        return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input);

    return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input) ||
            _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input);
    }

一个测试用例:

Sorted args: 1 2 3 4 5 6 7 8 9 10 11 12 : 
Start: 0, count: 12, mid: 5 value: 6
    Start: 0, count: 5, mid: 2 value: 3
        Start: 0, count: 2, mid: 0 value: 1
            Start: 1, count: 1, mid: 1 value: 2
        Start: 3, count: 2, mid: 3 value: 4
            Start: 4, count: 1, mid: 4 value: 5
    Start: 6, count: 6, mid: 8 value: 9
        Start: 6, count: 2, mid: 6 value: 7
            Start: 7, count: 1, mid: 7 value: 8
        Start: 9, count: 3, mid: 10 value: 11
            Start: 9, count: 1, mid: 9 value: 10
            Start: 11, count: 1, mid: 11 value: 12

上面是我的程序根据它的搜索方式运行的一些输出。对于 1 - 12 的列表，它围绕索引 5 旋转，确定在索引 0-4 处可能存在 0-4 之间的值。它还确定在索引 6-11 处可能存在 6-11 之间的值。因此，我继续搜索它们。这是错误的吗？

Answer 1

整数是不同的和排序的。

鉴于我这样array[i] = i你有array[i] - i = 0 .

对于每个 j < i 你有 array[j] - j <= 0对于 j > i 你有 array[j] - j >= 0因为 j 在每一步变化 1，但 array[j] 变化至少 1(不同且排序的数字)。

所以在左边是<=0右边是>= 0 .

使用二分法，您可以轻松找到 O(log n) 中的正确位置.

---

请注意，您只需要找到一个元素，而不是所有元素。在您的示例中，所有元素都在工作，但您只需要其中一个。如果你想打印它们，它将是 O(n) ..