javascriptarrays

Elegant way to find contiguous subarray within an array in JavaScript?


I wanted to write a function to find a contiguous subarray within a given array from a given starting index and return the index of the subarray within the array if it's found, and -1 if it's not found. This is similar to String.indexOf, but for arrays and subarrays instead of strings and substrings.

This is my working code:

var find_csa = function (arr, subarr, from_index) {
    if (typeof from_index === 'undefined') {
        from_index = 0;
    }

    var i, found, j;
    for (i = from_index; i < 1 + (arr.length - subarr.length); ++i) {
        found = true;
        for (j = 0; j < subarr.length; ++j) {
            if (arr[i + j] !== subarr[j]) {
                found = false;
                break;
            }
        }
        if (found) return i;
    }
    return -1;
};

And these are my tests and their expected values:

console.log(find_csa([1, 2, 3, 4, 5], [2, 3, 4]) === 1);
console.log(find_csa([1, 2, 3, 4, 5], [5]) === 4);
console.log(find_csa([1, 2, 3, 4, 5], [1, 3]) === -1);
console.log(find_csa([1, 2, 3, 4, 5], [42]) === -1);
console.log(find_csa([1, 2, 3, 4, 5], []) === 0);
console.log(find_csa([3, 4, 3, 4, 3, 4], [3, 4, 3], 1) === 2);
console.log(find_csa([6, 6, 6, 7], [6, 6, 7]) === 1);
console.log(find_csa([12, 9, 16, 42, 7, 866, 3], [16, 42, 7, 866]) === 2);

My code passes the tests, but as you can see, it uses a boolean value found in the inner loop which is just my messy, ad-hoc way of continuing an outer loop from a nested loop. is there a cleaner way of writing it? I looked into Array.prototype.findIndex but it is an experimental technology at the moment so I can't use it. I want a method that works in most browsers. I know there is a "polyfill" code snippet written on the Mozilla page, but that is even longer than my current code and it will be slower due to the function calls, so I'd rather avoid it.

My primary goal for this function is performance (the subarrays will be very small, so I believe that using Boyer-Moore string search algorithm or tries is a tad overkill), and then my secondary goal is elegance of my implementation. With those two goals in mind, I would like to know if there is a better way of writing this code, or if there are any JavaScript features or functions that I'm missing that could help me avoid the found boolean.

JSFiddle if it helps anyone: http://jsfiddle.net/qc4zxq2p/


Solution

  • Are there any JavaScript features or functions that I'm missing that could help me avoid the found boolean

    Yes, you can use a label on your outer loop:

    function find_csa(arr, subarr, from_index) {
        var i = from_index >>> 0,
            sl = subarr.length,
            l = arr.length + 1 - sl;
    
        loop: for (; i<l; i++) {
            for (var j=0; j<sl; j++)
                if (arr[i+j] !== subarr[j])
                    continue loop;
            return i;
        }
        return -1;
    }