Как разработать алгоритм «разделяй и властвуй», чтобы проверить, существует ли в массиве пара ai, aj, такая, что ai-aj = M?

Question

Учитывая список целых чисел a1, a2, ..., an, напишите алгоритм, который проверяет, существует ли пара ai, aj такая, что ai-aj = M. Сложность алгоритма во времени должна быть O (nlogn ) или лучше. Насколько мне известно, когда проблема ai + aj = M, эту проблему очень легко решить. Но сейчас у меня неприятности, когда состояние aaij = M.

Answer 1

Вы можете решить эту проблему, используя два алгоритма «разделяй и властвуй».

Сначала отсортируйте набор с помощью сортировки слиянием, которая является O (logn).

Затем, один за другим, вы можете посмотреть на элемент ai и посмотреть, является ли M-ai, который будет aj, элементом. Поскольку массив отсортирован, вы можете запустить двоичный поиск, который также является алгоритмом «разделяй и властвуй» и выполняется в O (logn). В худшем случае вам нужно будет сделать это n раз, по одному разу для каждого элемента в списке.

Следовательно, время работы этого алгоритма составляет O (logn + n * logn) = O (nlogn)