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

Question

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?

Answer 1

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.