Foundations of Algorithms and Data Structures (Fall 2018)

Handin - Searching an infinite list

Assume we have an infinite long sorted sequence of integers x₁ < x₂ < x₃ < ··· < 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₀ = -∞ if y < x₁).

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_is is a function of the final value of d. What is the most efficient algorithm (fewest number of comparisons) you can find?

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