Closest number out of two arrays

Former Member over 9 years ago

Have tried to make a function that gets the closest values out of two arrays, but sometimes i get "array out of bounds error".

example:
arr2 = [10, 20, 30, 40, 50];
arr = [1,2,8,21];

function closest (arr2, arr) {

        

      var arrayValue = new [2];

       

        for (var x = 0; x < arr2.size(); x++) {

	        

	        var curr = arr[0]; // error comes to this line

	        var num = arr2[x].toNumber();

	        var diff = (num - curr).abs();

			

	        for (var val = 0; val < arr.size(); val++) {

	            var newdiff =  (num - arr[val]).abs();

	            if (newdiff < diff) {

	                diff = newdiff;

	                curr = arr[val];

					arrayValue = [x, val];

	            }

	        }

        }

        return arrayValue;

	}

Thx for help!! :D

Former Member over 9 years ago

When you get this error on the stated line, it is very likely that your second array contains no elements. Make a sanity check at the top of your method like this:

if (arr. size() == 0 || arr..size() == 0) {

    return;

}

lcj2 over 9 years ago

If you change your loop code to look like below it should help you avoid out of bounds issues.

function closest (arr2, arr) {
    var arrayValue = new [2];
       
    for (var x = 0; x < arr2.size(); x++) {
        var x_val = arr2[x].toNumber();
        
        for (var y = 0; y < arr.size(); y++) {
	    var y_val = arr[y].toNumber();

            // all comparison code here
            
        }
    }
    
    return arrayValue;
}

lcj2 over 9 years ago

You could try the following. I spot checked but it worked for me with your example numbers. It has a few issues:

- need to check for null result returned if arrays are empty
- assumes arrays being entered are numbers
- won't report if more than one possible result set exists

function closest2(a1, a2) {
        var result = null;
        var smallestDiff = null;

        for (var x = 0; x < a1.size(); x++) {
            var x_val = a1[x].toNumber();

            for (var y = 0; y < a2.size(); y++) {
                var y_val = a2[y].toNumber();

                if (smallestDiff == null || (x_val - y_val).abs() <= smallestDiff) {
                    smallestDiff = (x_val - y_val).abs();
                    result = [x,y];
                }
            }
        }

        return (result);
    }

I get the following.

a1 = [10, 20, 30, 40, 50]
a2 = [1, 2, 8, 21]
result = [1, 3]

Former Member over 9 years ago

The time complexity for these solutions is O(n^2), because for all elements in a1 you iterate over all elements in a2.
I tested the algorithm in a data field and the watchdog killed the app in onUpdate for >250 elements in each array.

If and only if your arrays are sorted, you can find the closest pair in linear time O(n+m). Otherwise you must sort the arrays first and the overall time complexity is O(n log n).
Here is the solution:

function closest3(P, Q) {
        var lenP = P.size(); // assume > 0
        var lenQ = Q.size(); // assume > 0

        var diff = Math.pow(2, 31); // max number
        var _closest = [0, 0];
        var p = 0, q = 0;

        while (p < lenP || q < lenQ) {
            var newDiff = (P[p] - Q[q]).abs();

            if (newDiff < diff) {
                _closest = [p, q];
                diff = newDiff;
            }

            if (diff == 0) {
                break;
            }

            if (P[p] <= Q[q]) {
                p++;
            } else {
                q++;
            }
        }
        return _closest;
    }

With closest3 you can sort as much elements as you want (= until you get out of memory error) in under 1 second :) So no problem in data fields.