divide et impera problem

Given a set M, find if there is a pair of numbers (a,b), both belon开发者_运维问答g to M, and a+b=x, where x is a previously specified parameter. The problem should be solved using Divide et Impera in O(n * log n). Probably the problem should be split in two half-sized subproblems and then recombine the results in O(n).

I would like a pseudocode for the given problem or a tip for solving it.

Not sure if this fits your requirements, but:

1. Mergesort the set (this uses divide and conquer).
2. Start with the first and last elements of the set, and compare their sum to x. If the sum is equal, you are done. If the sum is larger, step down to the second last element, if the sum is smaller, step up to the second element.
3. Repeat step two, working in from the ends to the center of the sorted set, until the elements summing to x are found, or there are no more elements.

The divide and conquer sort is O(n lg n), the stepping through the sorted set is O(n), therefore total complexity O(n lg n).

Ed: sum to x, not M.

If you sort M (in O(n log n), using D&I), you can check in linear time if there's a pair with the right sum. (Hint: two pointers).

If you don't think that will count as a D&I solution, you can fold the checking step into the combine step of the sort and exit early if you find a match.

Addition: If you do the checking during the combine, you end up doing O(n log n) add-and-compare steps instead of O(n) -- but of course that doesn't worsen the asymptotic runtime except for the constant factor.