## 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)).