minimum absolute difference between two numbers in an array [closed]

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 5 years ago.

Improve this question

Gi开发者_如何学运维ven two arrays, A and B, i want to find a number from A and a number from B, such that the absolute difference between the two numbers is the smallest.

Eg

A = 1 2 9
B=  4 5  6

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

---

Sort the two arrays, then iterate them in parallel: For each item in A, search the closest item in B by a linear search. Start the linear search in B where you stopped for the previous item of A. Always remember the minimal distance found so far.

The time complexity is O(m log m + n log n) for sorting and O(m + n) for the final search, where m and n are the respective lengths of A and B.

---

it could be done in O(nlogm + mlogm)=O(nlogm):
(m is the smallest array`s length)
assume B is the smaller array

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

(*) binary search stops when you are closest to the number (or finds it if it exists)
checking first which is smaller (A or B) will ensure better performance.-

---

check this, maybe it gives you an idea so you adapt it to your needs:

#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;
} 

you would call it, having a structure:

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

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

---

I am making the assumption that the numbers in the Array will be floats. In 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

I am not an algorithm guru but that must work (haven't checked out). Hope I helped!

---

1. Sort both arrays
2. Combine the two numbers using some tag to differentiate 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 the consecutive terms with different tag. Ans: 2a 4b.