查找是否存在i的算法，以使array[i]等于i

Question

我收到了我的CS教授的作业：

在O(logn)时间中，如果在给定的由不同整数组成的预先排序数组中有一个索引i，则arrayi = i.证明时间是O(logn)。

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

好吧，所以我有点纠结于这件事。我的想法是：

使用二进制搜索，只有当arraymid <= startindex，其中mid是中间元素的索引，startindex是数组的开始时，才能确定中间元素左侧没有这样的值。

数组的右半部分对应的规则是arraymid >= 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。

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

左边是<=0，右边是>= 0。

使用二分法，您可以很容易地找到正确的位置在O(log n)。

​

请注意，您只需要找到一个元素，而不是所有元素。在您的示例中，所有元素都正常工作，但您只需要其中一个元素。如果你想把它们全部打印出来，那就是O(n)。

​

Answer 2

想象一下二进制搜索，就像在字典中查找一个单词。首先，你可以把这本书打开到字典的中心，看看页面顶部的单词是在前、后还是等于你要找的单词。如果是后面，你把字典的后半部分分成两部分，并检查那一半的中间部分。在查看了页面的顶部之后，你将搜索的范围缩小到了大约四分之一的字典范围内。继续这个过程，直到您发现这个单词在您正在查看的页面的某个位置。然后使用类似的过程在页面上找到单词。

这个过程不是O(n)，因为您不必查看每个页面上的每个单词，即使是在最坏的情况下。这是O(log )，因为通过每一步，您都可以删除字典中大约一半的内容，因为它不包含您要查找的单词。

编辑

对不起，我误解了原来的问题。

在这种情况下，关键是要认识到所谓的“鸽子洞原理”，即你只能把尽可能多的鸽子放进洞里，因为你有洞可以把它们放进去。(让学术界为这么简单的想法想出一个名字吧！)

考虑以下情况：

0 1 2 3 4 5 6

在这里，所有的array[i]都等于i，所以当您第一次开始二进制搜索时，您将立即得到一个肯定的答案。

现在让我们从底部取一个数字：

0 1 3 4 5 6

当您执行二进制搜索时，您会发现这个array[3] > 3，并且您可以正确地推断出，在这个枢轴点之上的任何值都不可能使array[i] == i。这是因为列表是有序的和唯一的，所以您不能以这样的组合结束：

0 1 3 4 5 5 6
0 1 3 4 6 5 7

一旦array[i]被确定为大于i，i和任何给定的n之间就没有足够的数字来允许数组中的下一个元素接近i。同样，如果您确定array[i]小于i，那么在查看数组的开头时，您没有足够的“空白”来“赶上”i。

因此，在每一步中，您都可以正确地消除数组的一半，就像查找字典一样，确定在O(log )时间内是否有任何array[i] == i。

Answer 3

这是一个二进制搜索问题，的密钥不给。在OP的问题中，关键是中间本身！就是这样，在每个子数组中搜索中间元素。

使用二进制搜索的解决方案的伪代码：

    while (low and high don't meet)
        mid = (low + high) / 2
        if (arr[mid] < mid)
            high = mid - 1
        else if (arr[mid] > mid)
            low = mid + 1
        else // we found it!
            return mid;
    // end while
    return -1; // indicates there is no such i