Rechercher un tableau trié pour trouver les valeurs les plus proches $ k $ d'une valeur cible $ t $

Question

Soit $ un $ un tableau trié de valeurs N $. Je suis intéressé à trouver l'index $ j $ tel que les éléments $ a_j, a_ {j + 1}, ..., a_ {j + k - 1} $ ont les valeurs les plus proches de $ k $ de la valeur cible donnée $ T $. Supposons que $ k $ est comparable, en amplitude, à $ n $; c'est-à-dire nous ne le faites pas avoir $ k ll n $.

On peut le faire naïvement par d'abord (binaire) à la recherche de l'élément le plus proche, puis de sonder successivement les voisins gauche / droite de cet élément pour arriver au résultat. Cette méthode a une complexité temporelle de $ o ( log n + k) $.

Je soupçonne que l'on peut modifier l'algorithme de recherche binaire d'origine pour arriver au résultat de $ o ( log n + log k) $ time. J'ai essayé de rechercher en ligne une telle variante de l'algorithme de recherche binaire, sans succès. J'apprécierais tous les pointeurs pour des sources que j'aurais pu manquer, ainsi que des tentatives originales de formuler une telle variante.

Noter: Il s'avère qu'il existe un cousin de recherche binaire élégant qui calcule le résultat de $ o ( log (n - k)) Voir la réponse d'Ivan Smirnov pour une discussion.