Suppose that you are given a very large array A[1..] of integers (think about A as being infinite size), in which the integers appear in increasing order (sorted) starting at position 1 in the array. The number of integers stored in the array, however, is unknown to you; that is, you are not given the index of the last integer in the array. You can assume that the remaining part of the array (after the last integer) is filled with the symbol *.

Design an algorithm that, given an integer key, decides whether key is in A by making O(lg (# integers in A)) comparisons; that is, the number of comparisons performed by your algorithm should be logarithmic in the number of integers stored in the array, Again, the number of integers in the array is not given to you.