>количество запросов многократно превышает размер массива
Сортировка работает за O(n*log(n)), бинпоиск будет работать за O(log(n)). Суммарная сложность будет O(n*log(n)) при количестве запросов порядка n.
Поиск полным перебором будет работать за O(n) для каждого запроса. Суммарная сложность будет не лучше O(n ^ 2), что очевидно хуже.
Быстрее можно только с построением hash-таблицы. Но это дополнительная память и не «Разделяй и Властвуй».
