Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))

Question

Given a sorted array $A[1,\ldots,n]$ and element $x$ that located at position $k$. We know $x$, we don't know $k$. Write an algorithm that finds $k$, in $O(\min(\log k, \log(n-k))$ time complexity.

Any ideas how to solve this?

Answer 1

The basic idea, when we don't know $k$, is to ask for elements with an exponentially growing index. The most natural here is some use of powers of two. For example, we can ask for elements with indices $1$, $2$, $4$, $8$, $16$, $\dots$. Or with indices $1$, $3$, $7$, $15$, $31$, $\dots$. This way, it will take $O (\log k)$ steps to arrive at the first element greater than $x$.

After we found two boundaries for $k$, do a regular binary search between them. If we asked for consecutive powers of two, the length of the interval is also $O (k)$, and the binary search will complete in $O (\log k)$.

When we know that $n - k$ is small, we can do the same but down from $n$, instead of up from $1$. That is, first ask for elements at indices $n$, $n - 1$, $n - 3$, $n - 7$, $\dots$. Once we hit an element less than $x$, do a regular binary search between the boundaries we found.

Lastly, what to do when we don't know whether $k$ is small or $n - k$ is small, but want to complete using the fastest of the two? Just run the searches in parallel. That is, ask for element $1$, then $n$, then $2$, then $n - 1$, then $4$, then $n - 3$, and so on. Naturally, either an odd question gives us an element greater than $x$, or an even question gives us an element less than $x$, in $O (\log (\min (k, n - k)))$. Proceed then with the regular binary search.

Answer 2

Check the first element. Then check the last. Then the second, then the second to last, then the fourth, then the fourth to last, then the eighth, and so on. Stop upon bounding the location of x to a region at the front or back of the list.

Once you've bounded it you can just do a binary search.

Can you see why this works?

Answer 3

You can apply binary expanding search starting from both ends of the given array.

For ease of statement, I will assume $n=2^k$ for some integer $k\ge0$. Otherwise, a boundary check can be included in step 3.1. I will assume the given array is sorted from small to large; otherwise, one comparison between $a_1$ and $a_n$ can be done to find the sorting order and the procedure can be adjusted accordingly.

1. Check if $x=a_1$ or $x=a_n$. If yes, return 1 or $n$ accordingly and stop.
2. Let $i=1$.
3. Loop the following.
   1. Is $x\le a_{2^i}$?
      • If yes, do a binary search for $x$ between $a_{2^{i-1}}$ exclusively and $a_{2^i}$ inclusively. Return the index and stop.
   2. Is $x\ge a_{n-2^i+1}$?
      • If yes, do a binary search for $x$ between $a_{n-2^{i}+1}$ inclusively and $a_{n-2^{i-1}+1}$ exclusively. Return the index and stop.
   3. increase $i$ by 1.