Пара позиций с заданным алгоритмом суммирования в O (n * log (n)) сложности времени

Question

Меня просят реализовать этот алгоритм в квадратичной, nlogn и линейной сложности.

Я выполнил квадратичную и линейную реализации, но не могу найти решение для nlogn.

С учетом упорядоченного массива (v) и целого числа (k) программа должна вывести упорядоченную пару индексов так, чтобы i было меньше j, а v [i] + v [j] == k;если пара не существует, вывод должен быть "(-1, -1)".

private static String linearSumPositionPair(int[] v , int k){
        int i=0;
        int j=v.length-1;
        String r="(-1, -1)";
        while(v[i]<v[j]){
            if(v[i]+v[j]==k){
                r="("+i+", "+j+")";
                break;
            }else if(v[i]+v[j]<k){
                i++;
            }else{
                j--;
            }
        }
        return r;
    }