Cerca un array ordinato per trovare i valori più vicini $ k $ a un valore target $ t $

Question

Lascia che $ A $ sia un array ordinato di valori $ n $. Sono interessato a trovare l'indice $ j $ in modo tale che gli elementi $ a_j, a_ {j + 1}, ..., a_ {j + k - 1} $ abbiano i valori più vicini $ k $ al valore target indicato $ T $. Supponiamo che $ k $ sia comparabile, in grandezza, a $ n $; cioè noi non avere $ k ll n $.

Si può fare ingenuamente questo con la prima (binaria) alla ricerca dell'elemento più vicino, quindi sondando successivamente i vicini sinistra/destra di quell'elemento per arrivare al risultato. Questo metodo ha una complessità temporale di $ O ( log n + k) $.

Sospetto che uno possa modificare l'algoritmo di ricerca binaria originale per arrivare al risultato in $ O ( log n + log k) $ tempo. Ho provato a cercare online una tale variante dell'algoritmo di ricerca binaria, senza successo. Apprezzerei qualsiasi/tutti i suggerimenti per le fonti che avrei potuto perdere, e anche i tentativi originali di formulare una tale variante.

Nota: Si scopre che c'è un elegante cugino di ricerca binaria che calcola il risultato in $ O ( log (n - k)) $ tempo. Vedi la risposta di Ivan Smirnov per una discussione.