You are given an in? nite array a[? ] in which the ? rst n cells contain integers in sorted order and the rest of the cells are ? filled with 1. you are not given the value of n. describe an algorithm that takes an integer x as input and ? nds 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 in? nite 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 1 whenever elements a[i] with i > n are accessed.)