Предоставление алгоритма, который выполняется с O (nlogn) для решения следующей проблемы

Question

Напишите алгоритм O (n lg n), который получает в качестве входных данных массив A из n действительных чисел, отсортированных в неубывающем порядке, и значение, val. Алгоритм возвращает true, если существуют различные индексы i и j, такие что a [i] + a [j] = val, и false в противном случае.

Я понял следующий псевдокод, но понял, что он работает только для соседних элементов

checkArray(Array A, val)    
if  A.length==2        
if A[0] + A[1] =val
return true;        
else  
return false       
else   
L1 = checkArray (A[0 : n/2],val) 
L2 = checkArray(A[n/2 : n], val)

Answer 1

Подсказки в комментариях в значительной степени выдают ответ O(nlogn) для каждого элемента a[i] и выполняют двоичный поиск в массиве, чтобы определить, существует ли val - a[i].Я не буду вдаваться в подробности об этом алгоритме, так как он кажется довольно простым.Вместо этого я хотел бы пролить свет на решение O(n), которое может быть не столь очевидным.

Короче говоря, O(n) использует два указателя, которые будут проходить от концов кпосередине, постоянно проверяю, совпадают ли две суммы до val.Если их сумма больше, чем val, мы уменьшаем большее из двух (самый правый указатель), перемещая его указатель влево.Если его меньше, мы увеличиваем меньшее из двух, перемещая указатель вправо.Если два указателя проходят друг через друга, мы знаем, что решения не существует.

checkArray(Array A, val)
    indexLo = 0
    indexHi = len(A) - 1
    while indexLo <= indexHi
        sum = A[indexLo] + A[indexHi]
        if sum == val
            return True

        if sum < val
            indexLo += 1
        else
            indexHi -= 1
    return False