current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 6 down vote favorite

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);

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 writing an early-breaking nested for 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 is 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/0g20pgrm/

share|improve this question
    
What about 1. JSON.stringify 2. array.prototype.slice –  zerkms 3 hours ago
    
Don't join with '' but join with , instead. String.indexOf would still work but it will avoid interpreting [2,11,5] and [21,15] as the same thing –  slebetman 3 hours ago
    
@zerkms, I could see JSON.stringify working to find the existence of a contiguous subarray, but do you know how you would retrieve its index? I'm guessing you would have to split on commas or something..but then you would be back to square 1. At your number 2 method, I fail to see how Array.prototype.slice would help. I understand you can use it to convert Strings into arrays using call but that is not the problem. –  Shashank 3 hours ago
    
@Shashank I've come up with a different approach. See if it satisfies your need –  mohamedrias 3 hours ago
    
@slebetman Good point...but I want the index of the subarray within the original array. Not the index of the substring within the string... [12, 44, 65].join(',') yields '12,44,65' but then searching for [44,65].join(',') using String.indexOf gives you 3 since it starts at the first character, not 1. I've removed the Array.prototype.join method from my question because I don't think it will work for values that translate to different length strings like 9999 for example. –  Shashank 3 hours ago

3 Answers 3

up vote 6 down vote accepted

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;
}
share|improve this answer
    
Nice, but I have two questions, what is the >>> syntax that you're using? Is that a standard way to set default argument values? Also is the use of labels considered bad practice? The reason I ask is because it says to avoid using them here: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… –  Shashank 3 hours ago
    
Not standard, >>> 0 is a hacky way of saying "convert to integer". x >>> y is "shift x to the right y bits"; if you shift 0 bits, it's the same thing you had before, but since >>> only works on integers you get the sideeffect of coercion to an integral value. It's probably the fastest way of doing it, along with x|0 (which does the same thing, AFAIK). Of course, assuming that your arguments are already integers is even faster, if you know the caller will obey the contract. :) –  Amadan 3 hours ago
    
@Shashank: The >>> unsigned bitshift is used to cast the from_index to an array-length integer. Labels are totally safe, it seems some people don't understand how they work and try to avoid this feature. –  Bergi 3 hours ago
up vote 5 down vote

This is the same as yours, just prettified a bit (at least to my aesthetics):

var find_csa = function (arr, subarr, from_index) {
    from_index = from_index || 0;

    var i, found, j;
    var last_check_index = arr.length - subarr.length;
    var subarr_length = subarr.length;

    position_loop:
    for (i = from_index; i <= last_check_index; ++i) {
        for (j = 0; j < subarr_length; ++j) {
            if (arr[i + j] !== subarr[j]) {
                continue position_loop;
            }
        }
        return i;
    }
    return -1;
};
share|improve this answer
1  
I like this answer. I did not know there were labels in JS. That certainly does clean up my code a bit. Though on the Mozilla documentation for labels it warns against using them. Is it considered bad practice? –  Shashank 3 hours ago
    
stackoverflow.com/questions/46496/… - tl;dr: if the program is more understandable and more concise when using a label, use a label (but it often isn't). –  Amadan 3 hours ago
up vote 2 down vote

The inner loop can be reduced to a single line using the array method every:

if(subarr.every(function(e, j) { return (e === arr[i + j]); })
    return i;

or (ES6 proposal):

if(subarr.every( (e, j) => (e === arr[i + j]) ))
    return i;

But this may be just a curiosity or educational example, unless you don't care about performance.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.