Assume we have an infinite long sorted sequence of integers
*x*_{1} <
*x*_{2} <
*x*_{3} <
··· <
*x*_{d-1} <
*x*_{d} <
*x*_{d+1} <
*x*_{d+2} < ··· and we
want to find the position of an integer *y* in this list, i.e. we
want to find the index *d*, such that
*y* = *x*_{d} if *y* is contained in the list, or otherwise if *y* is not in the list
the successor of *y* in the list, e.g. *x*_{d-1} <
*y* ≤
*x*_{d}
(here we assume *x*_{0} = -∞
if *y* < *x*_{1}).

**Example**: For the sequence
3
5
7
9
11
17
19
23
31
33
37 ...
and search value *y* = 11 the result is *d* = 5, whereas
for *y* = 24 the result is *d* = 9.

The task of this exercise is to find an efficient algorithm to
compute *d*, where the number of comparisons performed between *y* and the *x*_{i}s is a function of the final value of *d*. What is the most efficient algorithm (fewest number of comparisons) you can find?

- Describe an algorithm that finds the index
*d*. - Argue that your algorithm finds the
*correct*index*d*, such that either*y*=*x*_{d}or*x*_{d-1}<*y*<*x*_{d}. - Analyze your algorithm - how many comparisons does your
algorithm perform as a function of
*d*?