Description
Problem 1 (2.16 in DPV: finding x in an infinite array)
You are given an infinite array A[.] in which the first n entries contain different integers in sorted
order and the rest are filled with ∞. You are not given the value of n. Describe an algorithm that
takes as an input an integer x and finds a position in the array containing x, if such position exists,
in O(log(n)) time.
Problem 2 (2.17 in DPV: fixed point)
Given a sorted array of n distint integers A = {a1, a2, . . . , an}, you want to find out whether there
is an index i for which ai = i. Give a divide and conquer algorithm to solve this problems that runs
in time O(log(n)).