Find an element in an infinite length sorted array

The first approach will be linear in the index of the element (O(k) where k is the index of the element). Actually, you are going to need k/100 iterations to find the element which is greater than the searched element, which is O(k).

The second approach will be logarithmic in the same index. O(logk). (where k is the index of the element). In here, you are going to need log(k) iterations until you find the higher element. Then binary search between 2^(i-1), 2^i (where i is the iteration number), will be logarithmic as well, totaling in O(logk)

Thus, the second is more efficient.

You can apply binary search more or less directly with a small modification. This will roughly correspond to your Approach 2.

Basically, pick some number B and set A to 0, then check if the element you're looking for is between A and B. If it is, perform the usual kind of binary search in these boundaries, otherwise set B=A and A=2*A and repeat. This will take O(log(M)), where M is the position of the element you're looking for in the array.

If the array is well-founded, i.e. has a smallest element (i.e. you have elements x₀, x₁, ...), and all ele­ments are unique, then here's a simple approach: If you're looking for the number n, you can do a bi­na­ry search over the indices 0, ..., n − x₀. Note that we always have the basic inequality x_i ≥ i + x₀ for all i ≥ 0.

Thus you can find the value n in log₂(n − x₀) steps.