Foundations of Algorithms and Data Structures (Fall 2018)

Handin - Searching an infinite list

Assume we have an infinite long sorted sequence of integers x1 < x2 < x3 < ··· < xd-1 < xd < xd+1 < xd+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 = xd 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. xd-1 < yxd (here we assume x0 = -∞ if y < x1).

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 xis 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 = xd or xd-1 < y < xd.
  3. Analyze your algorithm - how many comparisons does your algorithm perform as a function of d?