fueanta

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