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.

 

[DeeNos]

I would like to offer a solution to this problem using a binary search algorithm. This algorithm works by dividing the sorted sequence into two halves and then checking if the middle element is equal to its index. If it is, then the algorithm terminates and returns the index. If not, then the algorithm compares the middle element to its index and determines whether the target element is in the left or right half of the sequence. This process is repeated until the target element is found or the algorithm determines that it does not exist in the sequence.

The time complexity of this algorithm is O(log n) because with each iteration, the size of the problem is halved, leading to a logarithmic time complexity. This makes it an efficient solution for determining whether there exists an i index such that ai = i.

In summary, the algorithm for this problem would involve using a binary search approach to divide the sorted sequence and compare the middle element to its index until the target element is found or determined to not exist. This would result in a time complexity of O(log n) making it an efficient solution for a simple problem.