2
$\begingroup$

Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A_j, A_{j + 1}, ..., A_{j + k - 1}$ have the $k$ closest values to the given target value $T$. Assume that $k$ is comparable, in magnitude, to $N$; i.e. we don't have $k \ll N$.

One can naively do this by first (binary) searching for the closest element, and then successively probing the left/right neighbors of that element to arrive at the result. This method has a time complexity of $O(\log N + k)$.

I suspect one can modify the original binary search algorithm to arrive at the result in $O(\log N + \log k)$ time. I tried searching online for such a variant of the binary search algorithm, without success. I'd appreciate any/all pointers to sources I might have missed, and also original attempts at formulating such a variant.

Note: It turns out there is an elegant binary search cousin that computes the result in $O(\log(N - k))$ time. See Ivan Smirnov's answer for a discussion.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ After finding the value closest to $T$, try performing another binary search (of a somewhat different kind) to find the $k$ closest values. The binary search will take an additional $O(\log k)$ essentially since you are searching among $2k$ values. What you are searching for is an interval of size $k$ around the value you found in the first binary search, and you are looking for the interval whose endpoints are closest to $T$. $\endgroup$
    – Yuval Filmus
    Jun 29, 2017 at 10:50

1 Answer 1

Reset to default
3
$\begingroup$

You can do it in two binary searches. For simplicity I assume that all numbers are distinct and, even more, absolute differences between $T$ and all other elements are distinct too. The solution is easily adapted if it is not the case.

What means that a selected subrange is optimal? That means that we can't move it neither right ($|A_{j+k} - T| > |A_{j} - T|$) nor left ($|A_{j+k-1} - T| < |A_{j-1}|$). That looks like a binary search as well!

Look at the function $h(j) = \mathbb{1}\{|A_{j+k} - T| > |A_{j} - T|\}$ (that is, $h(j)$ is 1 iff the answer does not become better if we move the subrange to the right). Now you have to find minimum $j$ s.t. $h(j) = 1$. As the function is monotonous, it can be done by a binary search by $j$ in $O(\log n)$ time. (Actually, it is $O(\log (n-k))$ because $j < n - k$).

If there are identical values in the array, we need some case handling. Whenever $|A_{j+k}-T| = |A_j-T|$, there are three cases possible: Either $A_{j} = A_{j+k}$ and the segment is to the left of $T$; in this case we should move right. Or, $A_{j} = A_{j+k}$ and the segment is to the right of $T$, and we should move left. Or the segment contains $T$, in this case we've found the optimal answer.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thanks for the answer! This is in line with what I was thinking. I've actually come up with another algorithm that ~~is asymptotically slightly better; i.e. it~~ runs in $O(\log(N - k))$ time. The difference only matters in cases where $k$ is close to $N$. I will add another answer that explains that approach. $\endgroup$
    – iheap
    Jun 30, 2017 at 18:56
  • $\begingroup$ @iheap You are welcome! By the way, my algorithm in fact also works in $O(\log (N-k))$ time because $j<N-k$. $\endgroup$
    – Ivan Smirnov
    Jun 30, 2017 at 18:57
  • $\begingroup$ Great. In my approach, I was searching for the optimal $j$ that minimizes $\max(|A_{j + k} - T|, |A_{j} - T|)$. This can be done in logarithmic time if all elements are distinct. If not, the algorithm might spend linear time, though. Does your method always take logarithmic time without the all-distinct assumption? $\endgroup$
    – iheap
    Jun 30, 2017 at 19:05
  • $\begingroup$ @iheap It should, if you replace $<$ with $\leq$ in one inequality and carefully think about invariants. To make your life easier try adding $-\infty$ to the beginning of the array and $+\infty$ to the end so you don't think about corner cases. $\endgroup$
    – Ivan Smirnov
    Jun 30, 2017 at 19:09
  • 1
    $\begingroup$ @iheap Let's try the following fix. We know that $A_j \leq T \leq A_{j+k}$. So whenever $|A_{j+k}-T| = |A_j-T|$, there are three cases: either $A_j = A_{j+k}$ and the segment is to the left of $T$; in this case we should move right. Or $A_j = A_{j+k}$ and the segment is to the right of $T$, and we should move left. Or the segment contains $T$, in this case we're done. I think that it fixes the binary search. $\endgroup$
    – Ivan Smirnov
    Jul 1, 2017 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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