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 < y ≤ xd (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 (and not the values of the numbers). What is the most efficient algorithm (fewest number of comparisons) you can find?