- #1

SpiffyEh

- 194

- 0

## 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?