C语言 查找是否有任何 i 的算法，以便 array[i] 等于 i

Algorithm to find if there is any i so that array[i] equals i

提问by Max

I've got an assignment from my CS professor:

我收到了 CS 教授的作业：

Find, in O(logn) time, if in a given pre-sorted array of distinct integers there is an index i so that array[i] = i. Prove that the time is O(logn).

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

Update:Integers can be negative, 0 or positive.

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

Alright, So I have struggled a bit with this. My idea is this:

好吧，所以我在这方面有点挣扎。我的想法是这样的：

Using binary search, we can only be certain that there is no such value to the left of the middle element if array[mid] <= startindex, where mid is index of middle element, and startindex is the start of the array.

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

Corresponding rule for the right half of an array is that array[mid] >= startindex + numel, where variables as above and numel is the number of elements right of mid.

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

This doesn't seem like O(logn), since in the worst case I have to iterate through the whole thing, right? Can someone tip me in the right direction here, or tell me this works?

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

Any ideas how I could formally prove this? I'm not asking for a definite answer, more some help to make me understand.

我有什么想法可以正式证明这一点吗？我不是在要求一个明确的答案，更多的是让我理解一些帮助。

In C:

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

A test case:

一个测试用例：

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

The above is my program run with some output according to how it searched. With a list from 1 - 12 it pivots around index 5, determines that there could be a value between 0-4 at indexes 0-4. It also determines that there could be a value between 6-11 at indexes 6-11. Thus, I proceed to search them both. Is this wrong?

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

回答by Lo?c Février

The integer are distincts and sorted.

整数是不同的和排序的。

Given i such that array[i] = iyou have array[i] - i = 0.

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

For each j < i you have array[j] - j <= 0and for j > i you have array[j] - j >= 0because j vary of 1 at each step but array[j] vary of at least 1 (distinct and sorted numbers).

对于每个 j < i 你有array[j] - j <= 0和对于 j > i 你有 array[j] - j >= 0因为 j 在每个步骤中变化为 1 但 array[j] 变化至少为 1（不同的和排序的数字）。

So on the left it's <=0on the right it's >= 0.

所以在左边它<=0在右边它是>= 0。

Using dichotomy you can easily find the correct position in O(log n).

使用二分法，您可以轻松找到O(log n).

---

---

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

回答by StriplingWarrior

Think of a binary search like looking up a word in the dictionary. You might start out by opening the book exactly to the center of the dictionary, and see whether the word at the top of the page is before, after, or equal to the word you're looking for. If it's after, you divide the latter half of the dictionary in two and check the middle of that half. After looking at the top of the page, you've narrowed down the area you're searching to within about a quarter of the dictionary. You continue this process until you find that the word is somewhere on the page you're looking at. Then you use a similar process to find the word on that page.

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

This process is not O(n) because you didn't have to look at every word on every page, even in the very worst-case scenario. It's O(log n) because with each step you were able to eliminate roughly half of the dictionary as notcontaining the word you were looking for.

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

Edit

编辑

Sorry, I misunderstood the original problem.

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

In this case, the key is to recognize the so-called "pidgeon-hole principle," which states that you can only fit as many pidgeons into holes as you have holes to fit them in. (Leave it up to academia to come up with a name for such a simple idea!)

在这种情况下，关键是要认识到所谓的“pidgeon-hole 原理”，该原理指出，您只能将与可以装入它们的孔一样多的 pidgeon 装入孔中。（留给学术界提出来）为这样一个简单的想法取了一个名字！）

Consider the following case:

考虑以下情况：

0 1 2 3 4 5 6

Here, allarray[i]are equal to i, so when you first begin your binary search, you'll immediately have a positive answer.

在这里，所有array[i]都等于i，因此当您第一次开始二分查找时，您将立即得到肯定的答案。

Now let's take a number away from the bottom:

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

0 1 3 4 5 6

When you do your binary search, you'll find that array[3] > 3, and you can correctly deduce that no value above that pivot point could possibly make array[i] == i. This is because the list is ordered and unique, so you can't end up with combinations like these:

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

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

Once array[i]is determined to be greater than i, there simply aren't enough numbers between iand any given nto allow the next element in the array to get any closer to i. Likewise, if you determine that array[i]is less than i, you don't have enough "gaps" available to "catch up" to ias you look toward the beginning of the array.

一旦array[i]确定大于i，就没有足够的数字i和任何给定的数字n来允许数组中的下一个元素更接近i。同样，如果您确定它array[i]小于i，那么i当您看向数组的开头时，就没有足够的“间隙”可以“赶上” 。

Therefore, on each step, you can correctly eliminate half of the array and, just like looking in a dictionary, determine whether any array[i] == iin O(log n) time.

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

回答by Rajendra Uppal

This is a binary search problem with key not given. In OP's question the key is mid itself! That's it, search for mid element in each subarray.

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

Pseudocode of the solution using Binary search:

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

    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

回答by Paul Sonier

Your intuition is right to use the binary search; your analysis is not. Remember it's a sorted list, so in the binary search condition, you need to search a MAXIMUM of log(n) entries.

使用二分搜索的直觉是正确的；你的分析不是。请记住，这是一个排序列表，因此在二进制搜索条件下，您需要搜索 MAXIMUM 个 log(n) 条目。

回答by Nathan Pitman

I'll try not to give away the answer but I'll point out a few observations:

我会尽量不透露答案，但我会指出一些观察结果：

When examining the middle element, there are 3 cases. The first is of course that array[i] == i, in which case the algorithm terminates. In the other two cases, we are able to discard the element itself as well as about half of the input.

在检查中间元素时，有 3 种情况。第一个当然是 array[i] == i，在这种情况下算法终止。在其他两种情况下，我们能够丢弃元素本身以及大约一半的输入。

Now, if array[i] > i, is it possible for the array index (i) to 'catch up' with the array values as we move to the right? Bear in mind the sorted distinct properties of the array values.

现在，如果 array[i] > i，当我们向右移动时，数组索引 (i) 是否有可能“赶上”数组值？请记住数组值的排序不同属性。

回答by Peiti Li

since array A is sorted. A[i]>=A[i-1]+1 => A[i]-i >= A[i-1]-(i-1), let B[i] = A[i]-i, B[] is a sorted array which can be searched for B[x]==0 in lgn time using binary search.

因为数组 A 已排序。A[i]>=A[i-1]+1 => A[i]-i >= A[i-1]-(i-1)，让 B[i] = A[i]-i， B[] 是一个排序数组，可以使用二分搜索在 lgn 时间内搜索 B[x]==0。

回答by Mark T

Array B[i] = A[i]-imay NOT be sorted even if A[i] is sorted but has duplicates:

Array B[i] = A[i]-i即使 A[i] 已排序但有重复项，也可能不会排序：

Consider this example:

考虑这个例子：

i: 0 1 2 3 4
A: 1 1 2 4 4

B[0] = A[0]-0 = 1, B[1] = A[1] -1 = 0 , ...

B: 1 0 0 1 0

我：0 1 2 3 4
A：1 1 2 4 4

B[0] = A[0]-0 = 1, B[1] = A[1] -1 = 0, ...

乙：1 0 0 1 0

回答by user3859492

public static int fixedPoint(int[] array, int start, int end) {

    if (end < start || start < 0 || end >= array.length) {
        return -1;
    }
    int midIndex = start +(end-start)/ 2;
    int midValue = array[midIndex];
    if (midValue == midIndex) {//trivial case
        return midIndex;
    }
    // if there are duplicates then we can't conclude which side (left or right) will
    // have the magic index. so we need to search on both sides
    //but, we can definitely exclude few searches.
    // take the example of the array : 
    //   0   1  2  3  4  5                        6  7  8  9   10 -> indices
    // -10, -5, 2, 2, 2, 3(midVal, midIndex = 5), 4, 7, 9, 12, 13 -> array element
    // here, midValue < midIndex, but we can't say for sure which side to exclude
    // as you can see there are two such magic indices. A[2] = 2 and A[7] = 7. so
    // we need to search both sides
    // since midValue < midIndex, then we can be sure that between index can't be
    // between index number midValue and midIndex-1

    /* Search left */
    int leftIndex = Math.min(midIndex - 1, midValue);
    int left = fixedPoint(array, start, leftIndex);
    if (left >= 0) {
        return left;
    }

    /* Search right */
    int rightIndex = Math.max(midIndex + 1, midValue);
    int right = fixedPoint(array, rightIndex, end);

    return right;
}

public static int fixedPoint(int[] array) {
    return fixedPoint(array, 0, array.length - 1);
}