How to apply the Divide and Conquer algorithm to an unsorted array?

Question

C++ / C#

So far the idea is only to sort the array, but I think it's not efficient
The problem I'm solving:
Write a program based on divide and conquer that allows you to effectively check whether a pair of values ​​belongs to an array. For example, the pair (2,3) belongs to the array [1,2,3,5,7,11,13,17], but the pair (3,4) does not. We can assume that the number of requests is many times greater than the size of the array. Write in the comments why brute force is effective

Answer 1

>number of requests many times exceeds the size of the array
Sorting works in O(n*log(n)), binsearch will work in O(log(n)). The total complexity will be O(n*log(n)) with the number of requests of order n.
A brute-force search will run in O(n) for each query. The total complexity will be no better than O(n ^ 2), which is obviously worse.
Faster is only possible with the construction of a hash table. But this is extra memory and not Divide and Conquer.