Mercurial > algorithms
view two_sum/two_sum_sort.cpp @ 5:d48b3fb142f0
Updated comments. Correct subtle logic error in two_sum_hash.cpp that would have resulted in bad output when there are repeated values in the input.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Mon, 04 May 2015 15:20:26 -0500 |
| parents | b06f215a4c69 |
| children |
line source
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.
4 // Solution: Sort the input data. For each value in the array, use binary
5 // search to see if (target - value) is also in the array, and if so print the
6 // pair of numbers. We need not consider values greater that target/2 since
7 // the the data is sorted, and (target - value) would have already been checked.
9 // Time performance is O(N log N) for the lookup, and varies for the sort,
10 // though here it is also O(N log N) giving O(N log N) overall performance.
11 // Space complexity if O(1), though, since no extra space is needed for the operations.
13 // Usage: Pass the target value as a command line option, and the number array as
14 // values on stdin, one item per line.
16 #include <algorithm>
17 #include <cstdlib>
18 #include <iostream>
19 #include <string>
20 #include <vector>
22 long binary_search( std::vector<long> vec, long lookfor, long min, long max ) {
23 while ( max >= min ) {
24 long mid = min + (max - min) / 2;
25 if ( vec[mid] == lookfor )
26 return mid;
27 else if ( vec[mid] > lookfor )
28 max = mid - 1;
29 else
30 min = mid + 1;
31 }
32 return -1;
33 }
35 void two_sum( std::vector<long> vec, long target ) {
36 std::sort( vec.begin(), vec.end() );
38 long lookfor;
39 long i = 0;
40 while ( vec[i] <= target/2 ) {
41 lookfor = target - vec[i];
42 long pos = binary_search( vec, lookfor, 0, vec.size()-1 );
43 if ( pos != -1 && pos != i ) {
44 std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << pos << ")" << std::endl;
45 }
46 i++;
47 }
48 }
50 int main( int argc, char **argv ) {
51 char *endptr = NULL;
52 long target = strtol( argv[1], &endptr, 10);
54 std::vector<long> vec;
55 long num;
56 std::string s;
58 while ( std::cin >> s ) {
59 num = strtol( s.c_str(), &endptr, 10);
60 vec.push_back(num);
61 }
63 two_sum( vec, target );
65 exit(EXIT_SUCCESS);
66 }