Algorithm for what should be a simple problem

[SpiffyEh]

Homework Statement

Suppose that you are given a sorted sequence of distinct integers {a1, a2, . . . , an}.
Give an O(lg n) algorithm to determine whether there exists an i index such as
ai = i. For example, in {−10,−3, 3, 5, 7}, a3 = 3. In {2, 3, 4, 5, 6, 7}, there is no
such i.

Homework Equations

The Attempt at a Solution

could this be done using a tree? For example splitting the problem in half with every iteration and checking to see if it is in the end? Or am I approaching this wrong?

 

[NobodySpecial]

O(ln) usually implies a divide-conquer approach
Try the half eah sequence and see what O() that has

 

[SpiffyEh]

i know halving it repeatedly gives O(log n) but I don't see how that gets me anywhere

 

[Mark44]

Here's a kind of rough outline. You have a sorted list of n numbers. Look at the middle of the list, and see whether a_n/2 == n/2. If so, you're done.

If a_n/2 < n/2, look in the lower half of the list.
If a_n/2 > n/2, look in the upper half of the list.

Do the above recursively, stopping when the size of the list is 1.

For example, suppose the list is {−10,−3, 3, 5, 7, 8 11, 12}. (I added a few numbers to your first example.)

Here n = 8

a₄ = 5, so we should look in the lower half of the list; i.e., a₁ through a₄.

Now n = 4
a₂ = -3, so we should look in the upper half of this list; namely, at a₃ and a₄

Now n = 2, and we see that a₃ == 3 and we're done.