Encontre números que tenham uma diferença específica em uma lista classificada

Dado N números ordenados, precisamos encontrar, se houver um par, com diferençaK.

A O(N log N) solução é verificar para cada númerox , verifique se (x + K) existe usandopesquisa binária.

Eu queria saber se existe um melhorO(n)tempo, e O (1) solução espacial para isso.