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

I've got an assignment from my CS professor:

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).

Update: Integers can be negative, 0 or positive.

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.

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.

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?

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:

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?

---

The integer are distincts and sorted.

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

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

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

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

---

Please note that you only need to find one element, not all of them. In your example all elements are working but you only need one of them. If you want to print them all it will be O(n)..

---

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 not containing the word you were looking for.

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!)

Consider the following case:

0 1 2 3 4 5 6

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

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:

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 i and any given n to 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 i as you look toward the beginning of the array.

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

---

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.

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

---

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.

---

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.

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.

---

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.

---

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

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

---

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

---

Input: Array A of sorted n distinct integers which can be positive, negative or zero.

Output: Return True if there is an index i such that A[i] = i, return False otherwise.

Running time: O(logN)

---

A divide-and-conquer strategy is used to divide the array in subarrays by halving it using a variable called midpoint. The goal is to recursively keep dividing the array in two branches until there is a single element left in each of the two branches.

When a single element is found by comparing the low and the midpoint indexes, the evaluation of A[i] = i takes place for the left and the right branches. As long as one of the two branches is True, the program ends.

In the recursive case:

return False or True  -> True
return False or False -> False
return True or  ----- -> True // Short-circuit operator: regardless of the right branch, the result will be True.

This code in Python can be easily written in C or any other language:

def isIndex(A, low, high):
    midpoint = int( (low + high)/2 )
    if low == midpoint:
        # base case
        print("Left-> low: %d, A[low]: %d. Right-> high: %d, A[high]: %d" % (low, A[low], high, A[high]))
        return low == A[low] or high == A[high]
    else:
        # recursive case
        return isIndex(A, low, midpoint-1) or isIndex(A, midpoint, len(A)-1)

A = [0, 1, 3, 5]
print(isIndex(A, 0, len(A)))
"""
Left-> low: 0, A[low]: 0. Right-> high: 1, A[high]: 1
True
"""

A = [-1, 0, 1, 3, 9, 10]
print(isIndex(A, 0, len(A)))
"""
Left-> low: 0, A[low]: -1. Right-> high: 0, A[high]: -1
Left-> low: 1, A[low]: 0. Right-> high: 2, A[high]: 1
Left-> low: 3, A[low]: 3. Right-> high: 3, A[high]: 3
True
"""