The minimum absolute difference between two numbers in an array

Question

Given the two arrays, A and B, I want to find a number from A and a number from B, so the absolute difference between the two numbers is the smallest.

For instance,

A = 1 2 9
B=  4 5  6

Ans: 2.4 as Math.abs (2-4) = 2

Answer 1

Sort the two arrays, then repeat them in parallel: for each element in Afind the nearest element in Busing a linear search. Run a linear search at Bwhere you left off for the previous item A. Always remember the minimum distance found so far.

- O (m log m + n log n) O (m + n) , m n - A B.

Answer 2

O (nlogm + mlogm) = O (nlogm):
(m - ) , B -

sort array B
minimum =  | A[0]-B[0] | 
for each a in A:
binary search for a in B - return the closest numbers let the numbers be b1,b2 (*)
if min{|b1-a|,|b2-a|} is smaller then the previous minimum - store it as the new minimum

(*) , ( , ) , (A B), .

Answer 3

, , , :

#define TOP 2147483647
#define true 1
#define false 0


/* finds the minimum (absolute value) of vector vec */

void Vector_Min_Not_0(vector *vec, int *min, int *index)
{
  int m, size, i, ind, aux;

  size = vec->size;
  m = TOP;
  ind = -1;
  for (i = 0; i < size; i++)
    if (vec->p[i] != 0)
      if (m > (aux = abs(vec->p[i]))) {
    ind = i;
    m = aux;
      }
  if (ind == -1)
    *min = 1;
  else
    *min = m;
  *index = ind;
} 

, :

typedef struct vector {
  int size;
  int *p;
} vector;

vector vec_A;
int min, index, *p;
Vector_Min_Not_0(&vec_A, &min, &index);

Answer 4

, . Ruby:

def smaller_abs(array1, array2)
  array1.product(array2).each_with_index do |ar,i|
      if i==0
        dif = (ar[0]-ar[1]).abs
        pair = ar
        next
      end
      pair = (ar[0]-ar[1]).abs > dif ? pair : ar
  end
  pair
end

, ( ). , !

Answer 5

• Sort both arrays
• Combine the two numbers using some tag to distinguish them. e.g. A = 1 9 2 B = 5 4 6

After sorting:

A = 1 2 9 B = 4 5 6

Combine the array: C = 1a 2a 4b 5b 6b 9a

Now do a linear search and find the difference between consecutive terms with a different tag. Ans: 2a 4b.