Question

Question: You are given an infinite array $\mathit{A}[·]$in which the first n cells contain integers in sorted order and the rest of the cells are filled with $\mathbf{\infty }$. You are not given the value of n. Describe an algorithm that takes an integer x as input and finds a position in the array containing x, if such a position exists, in O(log n) time. (If you are disturbed by the fact that the array A has infinite length, assume instead that it is of length n, but that you don’t know this length, and that the implementation of the array data type in your programming language returns the error message $\mathbf{\infty }$whenever elements $\mathit{A}\mathbf{\left[}\mathit{i}\mathbf{\right]}\mathbf{}\mathbf{}\mathbf{with}\mathbf{}\mathbf{}\mathit{i}\mathbf{>}\mathit{n}$ are accessed.)

Short answer

An algorithm exist which finds the position of input inter x in array A, in time bound of $O(logn)$.

Step-by-step solution

Algorithm  

1. Check $A\left[1\right],A\left[2\right],A\left[4\right],A\left[8\right],$, and so on, doubling its indexing each time until infinity or the value x is discovered. Let q be the most recent index to be examined.

2. If $x=A\left[q\right]$after back q.

3. If not, conduct a binary find in $A[q/2]...A\left[q\right]$for x. Give the index if x is found; else, return FALSE.

Binary Search Pseudocode

Each sub-array will be subjected to something like a binary search algorithm $A[q/2]...A\left[q\right]$

binary_search (A,x) :

low = 1, high = size(A)

while low $\le$high:

mid = low + (high - low)/2

if A[mid] == x:

return mid

else if A[mid] < x:

low = mid + 1

else:

high = mid - 1