Binaria Search - complexity

Question

Good afternoon, could someone help me with the discipline of algorithm complexity, to stopped in the question of binary search. Some can help me with the question below:

Consider again another variation of the binary search problem, write a algorithm to solve it and calculate its complexity. This time the search will take place in a sequence of unknown size as described. Given a theoretically infinite sequence X1 < x2 < X3 < X4 < ... and a z element, find the i such that xi = z.

Answer 1

As we know, the normal binary search algorithm works between two indexes, which are initially the first and last indexes of the array.

As you are working with an infinite array, there is no "last index". Therefore, we need to choose an index to be the top index, and from there apply the normal binary search. This index cannot be completely arbitrary. It is necessary to ensure that the searched element don’t show up after of the chosen index.

To preserve the asymptotic complexity of binary search, one can use the following algorithm to find an appropriate upper index in an infinite array:

(It is considered a language whose indexes begin in 0)

declare o índice inferior, inicialmente com 0
declare o índice superior, inicialmente com 2

enquanto o elemento no índice superior for menor que o elemento procurado
    o índice inferior recebe o índice superior
    o índice superior é dobrado

faça a pesquisa binária normal entre os índices inferior e superior

It is very important to note that this algorithm works only if the array elements are crescent, exactly as stated in the question:

a theoretically infinite sequence X1 < x2 < X3 < X4 < ...

Not every ordered array obeys this law. For example, an infinite array in which all elements are 1 can be considered ordered, but the above algorithm will loop infinity if the searched element is 2.