Problem
Given two sorted arrays of equal length,
how do you find a pair of numbers, one from each array,
such that the absolute difference between the two numbers is minimum.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find minimum absolute difference btween two numbers in 2 arrays
Created Data : 23-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <limits>
using namespace std;
pair<int, int> FindMinAbs(int* arr1, int len1, int* arr2, int len2)
{
int i(0), j(0);
long long minAbsDiff = abs((long long)arr1[i] - (long long)arr2[j]);
int a1 = arr1[0];
int a2 = arr2[0];
while(i < len1 && j < len2){
if(abs((long long)arr1[i] - arr2[j]) < minAbsDiff){
minAbsDiff = abs((long long)arr1[i] - (long long)arr2[j]);
a1 = arr1[i];
a2 = arr2[j];
}
if(arr1[i] == arr2[j]){
return pair<int, int>(arr1[i], arr2[j]);
}
else if(arr1[i] < arr2[j]){
i ++;
}
else{
j ++;
}
}
return pair<int, int>(a1, a2);
}
void DoTest(int* arr1, int len1, int* arr2, int len2)
{
cout << "Array 1" << endl;
for(int i = 0; i < len1; ++i){
cout << arr1[i] << " ";
}
cout << endl;
cout << "Array 2" << endl;
for(int i = 0; i < len1; ++i){
cout << arr2[i] << " ";
}
cout << endl;
pair<int, int> ret = FindMinAbs(arr1, len1, arr2, len2);
cout << "The pair are (" << ret.first << ", " << ret.second << ")" << endl;
cout << "---------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr1[] = {1, 7, 10, 20};
int arr2[] = {4, 5, 13, 21};
DoTest(arr1, 4, arr2, 4);
for(int i = 0; i < 4; ++i){
arr1[i] = numeric_limits<int>::min();
arr2[i] = numeric_limits<int>::max();
}
DoTest(arr1, 4, arr2, 4);
for(int i = 0; i < 4; ++i){
arr1[i] = i;
arr2[i] = numeric_limits<int>::max();
}
DoTest(arr1, 4, arr2, 4);
for(int i = 0; i < 4; ++i){
arr1[i] = numeric_limits<int>::max();
arr2[i] = numeric_limits<int>::max();
}
arr1[0] = 1;
DoTest(arr1, 4, arr2, 4);
return 0;
}
Output
Array 1
1 7 10 20
Array 2
4 5 13 21
The pair are (20, 21)
---------------------------
Array 1
-2147483648 -2147483648 -2147483648 -2147483648
Array 2
2147483647 2147483647 2147483647 2147483647
The pair are (-2147483648, 2147483647)
---------------------------
Array 1
0 1 2 3
Array 2
2147483647 2147483647 2147483647 2147483647
The pair are (3, 2147483647)
---------------------------
Array 1
1 2147483647 2147483647 2147483647
Array 2
2147483647 2147483647 2147483647 2147483647
The pair are (2147483647, 2147483647)
---------------------------
Press any key to continue . . .