$O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right Assume A is an m sized array containing n ($m \ge n$) natural numbers (excluding $0$), sorted on the left of it.
All remaining cells on right are filled with zeros.

For example, $m=10, n=4$:

$$A = \{5,7,11,24,0,0,0,0,0,0\}$$

How can I find the index of a natural number x in A with $O(\log \boldsymbol{n})$ complexity?

Edit: $n$ is not known.
A two-stage binary search works. First, for the purposes of this search define $0$ to be greater than any positive integer.

Then, let $l = 1$ and $h = 2$ and:


While $A_h \leq x$ let $l \leftarrow h$ and $h \leftarrow 2h$. Since for all $h &gt; n$ we have $A_h = 0$, which we defined to be greater than any positive number, this loop must exit within $O(\log n)$ iterations.
Now $A_l \leq x &lt; A_h$, and $A$ is sorted, so we can do a binary search in range $[l, h]$. This also takes $O(\log n)$ steps since $l,h \leq 2n$.