# G* Get the pair of a sorted list of which the sum is given.

May 29th, 2017
117
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2.
3. using namespace std;
4.
5. int closestSmallerSearch(int[], int, int);
6.
7. bool hasPair(int[], int, int[], int);
8.
9. int main(void)
10.
11. {
12.     int size = 0;
13.
14.     cout << "How many elements? : ";
15.     cin >> size;
16.
17.     int *arr = new int[size];
18.     int pairs[2] = { 0 };
19.
20.     for (int i = 0; i < size; i++)
21.     {
22.         cout << "\nElement no:" << i + 1 << " = ";
23.         cin >> arr[i];
24.     }
25.
26.     cout << "\n---------------------\n";
27.
28.     cout << "\nGiven sum : ";
29.     int sum = 0; cin >> sum;
30.
31.     if (hasPair(arr, size, pairs, sum))
32.     {
33.         cout << "\nFirst occurence of pair : (" << pairs[0] << ", " << pairs[1] << ")\n\n";
34.     }
35.     else
36.     {
37.         cout << "\nNo such pair is found.\n\n";
38.     }
39.
40.     return 0;
41. }
42.
43. int closestSmallerSearch(int list[], int size, int value)
44. {
45.     int low = 0, high = size - 1;
46.     int mid = 0;
47.
48.     while (low <= high)
49.     {
50.         mid = low + ((high - low) / 2); // (low + high) / 2
51.
52.         if (list[mid] == value)
53.         {
54.             return (mid - 1); // if matches then we need the index - 1 here
55.         }
56.         else if (list[mid] < value)
57.         {
58.             low = mid + 1;
59.         }
60.         else
61.         {
62.             high = mid - 1;
63.         }
64.     }
65.
66.     if (low == high) // if not matches , we need the smaller nearest
67.     {
68.         if (list[low] < list[mid])
69.         {
70.             return low;
71.         }
72.         else if (list[low] > list[mid])
73.         {
74.             return (low - 1);
75.         }
76.     }
77. }
78.
79. bool hasPair(int collection[], int size, int pairs[], int sum)
80.
81. {
82.     bool pairFound = false;
83.     int begin = 0, end = closestSmallerSearch(collection, size, sum);
84.     if (end != -1)
85.     {
86.         while (begin < end) {
87.             int total = collection[begin] + collection[end];
88.             if (total == sum)
89.             {
90.                 pairs[0] = collection[begin];
91.                 pairs[1] = collection[end];
92.                 pairFound = true;
93.                 break;
94.             }
95.             else if (total < sum)
96.             {
97.                 begin++;
98.             }
99.             else
100.             {
101.                 end--;
102.             }
103.         }
104.     }
105.     else
106.     {
107.         cout << "\nGiven sum is too small." << end;
108.     }
109.     return pairFound;
110. }
RAW Paste Data