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

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.

• Each comparison reveals 1 bit of information – Bulat Apr 14 at 13:23
• What do you mean? – motis10 Apr 14 at 13:27
• Bulat's hint is sort of cryptic. Here is a different hint. Can you find $n$ or any number that is between $n$ and $2n$ in $O(\log n)$ time? – Apass.Jack Apr 14 at 16:33
• If you find any number between $n$ or $2n$ (or any $cn$ for a constant $c\ge1$), you can treat that number as $m$. Then you can find a number by binary search with $O(\log m)=O(\log n)$. – Apass.Jack Apr 14 at 17:03
• Check positions number $1,2,4,8,\ldots$ until you find a zero. This takes time $O(\log n)$, and finds a position between $n$ and $2n$. You can then perform binary search as usual. – Yuval Filmus Apr 14 at 20:32

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,\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, A, \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.