$O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right
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$.