Как применить алгоритм «Разделяй и Властвуй» к неотсортированному массиву?

Question

[Jairman]

Пока идея только отсортировать массив, но, думаю, это не эффективно

Сама задача, которую я решаю:
Напишите программу на основе разделяй и властвуй позволяющую эффективно проверять принадлежность пары значений массиву. Например, пара (2,3) принадлежит массиву [1,2,3,5,7,11,13,17], а пара (3,4) - нет. Можно считать, что количество запросов многократно превышает размер массива. В комментариях напишите, почему перебор - эффективное

Answer 1

[tsarevfs]

>количество запросов многократно превышает размер массива
Сортировка работает за O(n*log(n)), бинпоиск будет работать за O(log(n)). Суммарная сложность будет O(n*log(n)) при количестве запросов порядка n.

Поиск полным перебором будет работать за O(n) для каждого запроса. Суммарная сложность будет не лучше O(n ^ 2), что очевидно хуже.

Быстрее можно только с построением hash-таблицы. Но это дополнительная память и не «Разделяй и Властвуй».

Comments

[T_g]

Мда, задачки пошли в народ. Это всего лишь упражнение на бин.поиск для десятиклашек. Кстати, оценка сложности - n log m, где m размер массива.

Answer 2

[vaut]

Перебор O(n)
Двоичный поиск на отсортированном массиве или двоичном дереве O(log n)