Infinite array A and finding the index of x:

Question: You are given an infinite array A[.] in which the first n cells contain integers in sorted orde and the rest of the cells are filled with INF. You are not given the value n Describe an algorithm that takes an integer x as input and finds a position in the array containing x, if such a position exists, in O(log n) time.


Answer: The idea is this:

1. Find the index of the end of valid elements, which is n, by using idea similar to binary search (keeping variables left and right, doubling the increment)
2. After getting n, just apply binary search on A[1...n]. Done.

Analysis: Find n by exponentiation takes O(log n). Binary search is O(log n). So, total time is O(log n).


Possible Solution Code (in Python):

The above code should output -1 and 8, as 13122313 is not there!