Given a set of S containing n real numbers, and a real number x. We seek an algorithm to determine whether two elements of S exist whose sum is exactly xFor the first case,
- Assume that S is unsorted. Give an O(nlogn) algorithm for the problem.
- Assume that S is sorted. Give an O(n) algorithm for the problem.
1st, sort the set with a O(nlgn) sorting algorithm.
2nd, go through every element in the set, for each element, use binary search to find (x - element) in the set.
For the second case,
1st, find the complementary array, which is subtracted each of array from x.
2nd, it's like walking face to face, and at some point, they will meet each other.