Home /
Expert Answers /
Computer Science /
you-are-given-an-infinite-array-a-in-which-the-first-n-cells-contain-integers-in-ascending-pa129

You are given an infinite array $A[?]$ in which the first $n$ cells contain integers in ascending order and the rest of the cells are filled with infinity. You are not given the value of $n$. Describe a divide $&$ conquer algorithm that takes an integer $x$ as input and finds a position in the array containing $x$, if such a position exists, in $O(gn)$ 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 "infinity" whenever elements $A[i]$ with $i>n$ are accessed.) A complete solution will (a) describe your algorithm in English (no pseudocode), (b) provide a justification of correctness (why does this approach work?), and (c) state and analyze its runtime in Big O notation, including a recurrence relation for it, if relevant.

APPROACH:We will use a vector of integers for storing the elements of array because we do not know the size of the array. ( Vector is basically a dyna