1 // Problem: given an input array of numbers, and a target value, find all pairs

2 // of numbers in the input which sum to the target value.

3

4 // Solution: Sort the input data. We can now use binary search to look up target numbers.

5

6 // Time performance is O(N log N) for the lookup, and varies for the sort,

7 // though here it is also O(N log N) giving O(N log N) overall performance.

8 // Space complexity if O(1), though, since no extra space is needed for the operations.

9

10 // Usage: Pass the target value as a command line option, and the number array as

11 // values on stdin, one item per line.

12

13 #include <algorithm>

14 #include <vector>

15 #include <string>

16 #include <cstdlib>

17 #include <iostream>

18

19 long binary_search( std::vector<long> vec, long lookfor, long min, long max ) {

20 while ( max >= min ) {

21 long mid = min + (max - min) / 2;

22 if ( vec[mid] == lookfor )

23 return mid;

24 else if ( vec[mid] > lookfor )

25 max = mid - 1;

26 else

27 min = mid + 1;

28 }

29 return -1;

30 }

31

32 void two_sum( std::vector<long> vec, long target ) {

33 std::sort( vec.begin(), vec.end() );

34

35 long lookfor;

36 long i = 0;

37 while ( vec[i] <= target/2 ) {

38 lookfor = target - vec[i];

39 long pos = binary_search( vec, lookfor, 0, vec.size()-1 );

40 if ( pos != -1 && pos != i ) {

41 std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << pos << ")" << std::endl;

42 }

43 i++;

44 }

45 }

46

47 int main( int argc, char **argv ) {

48 char *endptr = NULL;

49 long target = strtol( argv[1], &endptr, 10);

50

51 std::vector<long> vec;

52 long num;

53 std::string s;

54

55 while ( std::cin >> s ) {

56 num = strtol( s.c_str(), &endptr, 10);

57 vec.push_back(num);

58 }

59

60 two_sum( vec, target );

61

62 exit(EXIT_SUCCESS);

63 }

64

65