3
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Each comparison reveals 1 bit of information $\endgroup$ – Bulat Apr 14 '19 at 13:23
  • $\begingroup$ What do you mean? $\endgroup$ – motis10 Apr 14 '19 at 13:27
  • $\begingroup$ 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? $\endgroup$ – John L. Apr 14 '19 at 16:33
  • 1
    $\begingroup$ 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)$. $\endgroup$ – John L. Apr 14 '19 at 17:03
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 14 '19 at 20:32
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.