Searching a sorted array to find the $k$ closest values to a target value $T$ 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.
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| &gt; |A_{j} - T|$) nor left ($|A_{j+k-1} - T| &lt; |A_{j-1}|$). That looks like a binary search as well!

Look at the function $h(j) = \mathbb{1}\{|A_{j+k} - T| &gt; |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 &lt; 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.