找到是否有任何i以使array [i]等于i的算法

Question

我的CS教授已经完成了一项任务:

在O(logn)时间内,如果在给定的预先排序的不同整数数组中找到索引i,则array [i] = i.证明时间是O(logn).

更新:整数可以是负数,0或正数.

好吧,所以我对此有点挣扎.我的想法是这样的:

使用二分搜索,我们只能确定中间元素左侧没有这样的值,如果array [mid] <= startindex,其中mid是中间元素的索引,startindex是数组的开头.

数组右半部分的对应规则是数组[mid]> = startindex + numel,其中变量如上所示,numel是中间右边的元素数.

这似乎不是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但是数组[j]至少变化1(不同和排序的数字).

所以在左边它就<=0在右侧>= 0.

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

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

Answer 2

想想二元搜索,比如在字典中查找单词.您可以通过将书完全打开到词典的中心开始,然后查看页面顶部的单词是在您要查找的单词之前,之后还是等于.如果它在之后,你将字典的后半部分分成两部分并检查那部分的中间部分.查看页面顶部后,您在字典的四分之一范围内缩小了搜索区域的范围.您继续此过程,直到您发现该单词位于您正在查看的页面上的某个位置.然后,您使用类似的过程在该页面上查找单词.

这个过程不是O(n),因为你不必查看每个页面上的每个单词,即使是在最糟糕的情况下也是如此.它是O(log n)因为每一步都能消除大约一半的字典,因为它不包含你要查找的单词.

编辑

对不起,我误解了原来的问题.

在这种情况下,关键是要认识到所谓的"皮江孔原理",它表明你只能在洞中安装尽可能多的皮塞,因为你有适合它们的洞.(让学术界接受它有这么简单的想法的名字!)

考虑以下情况:

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在查看数组的开头时,没有足够的"间隙"可用于"赶上" .

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