Search a sorted array that ends with zeros in O(log n) time

Question

I have an array of size $m$, $[1,1,2,2,3,4,5,...,f,0,0, \cdots,0]$, where the first $n$ elements $1,1,2,2,3,4,5,\cdots, f$ are sorted.

If I make a binary search including the 0's I get $O(\log(m))$.
I'm trying to make the algorithm better and to get complexity of $O(\log(n))$ with no success.

I thought maybe something with medians?
Any idea will be great.

Answer 1

Here is a simple algorithm to solve the problem as in Yuval's comment.

Algorithm

Input: A positive number $w$ and array $A$ of $m$ numbers, $A[0],\cdots, A[m-1]$. The first $n$ numbers of $A$ are non-decreasing positive numbers and the rest are 0s.

Output: An index $k$ such that $A[k]=w$ or -1 if $w$ is not an element of $A$.

Procedure:

1. Check elements at index $1,2,4,8,\cdots$, until a zero is found or the index overflows. Let the index thus found be $p_0$. Let $p$ be the smaller of $p_0$ and $m-1$. Note $n\le p\lt 2n$.
2. Consider 0 as greater than all positive numbers so that $A[0], A[1], \cdots, A[p]$ becomes a sorted array. Conduct a binary search for $w$ on that array. If $w$ is found, return the index; Otherwise, return -1.

Algorithm analysis

Step 1 checks at most $\log_2(2n)=1+\log_2 n$ elements. Step 2 checks at most $\log_2(p+1) + 1 \le 2 + \log_2n$ elements. So the time-complexcity of the algorithm is $O(\log n)$.

This problem is a variation of the classic problem of searching sorted, unbounded/infinite lists. The algorithm above is a simple variation of the exponential search explained in this Wikipedia article. You are encouraged to take a look at that article for more intriguing variations. For example, a basic version of Bentley and Yao's algorithms checks elements at index 2, 4, 16, 256, 65536, $\cdots$ first.

Exercises

Exercise 1. (One minute or two) Assume that $w$ might not be positive and the first $n$ element of $A$ might not be positive instead. Adapt the algorithm slightly so that it still works.

Exercise 2. (One minute or two) Improve the algorithm so that it runs in $O(\log k)$ time where $k$ is the smaller of $n$ and the index of the first element in $A$ that is no less than than $w.$

Exercise 3. Let $B$ be a sorted array of $n$ distinct elements, one of which is $w$. Devise an algorithm that finds $w$'s index in $O(\min(k, n-k))$ time, where $k$ is $w$'s index.