We know we can do binary search on a sorted array A[1..n] in (log n) time. But what if we dont know the value n?

Your task in this problem is to give (log n)-time algorithm to search such an array for a target key K, returning the index in A of K, if it exists, or else -1. (You can assume for simplicity that the values of A are all distinct.)

Since you dont know As length, a common occurrence will be falling of the end of A, i.e., trying to access A[i] for an i greater than (the unknown value of) n. In programming doing this might return an error or throw an exception. For the purposes of this problem, it may be simpler to assume that A[i] will evaluate to when i > n, i.e., a comparison between A[n+ 1] and other actual key (either the target K or any A[k] for 1 k n will always say A[n + 1] is larger.