# Uint8Array indexOf method that allows to search for byte sequences

Uint8Array.prototype.indexOfMulti = function(searchElements, fromIndex) {
fromIndex = fromIndex || 0;

var index = Array.prototype.indexOf.call(this, searchElements[0], fromIndex);
if(searchElements.length === 1 || index === -1) {
return index;
}

for(var i = index, j = 0; j < searchElements.length && i < this.length; i++, j++) {
if(this[i] !== searchElements[j]) {
return this.indexOfMulti(searchElements, index + 1);
}
}

return (i === index + searchElements.length) ? index : -1;
};


It works fine but I wonder if I missed any important case or if anyone sees a way to optimize this.

-

First things first. This code is fairly difficult to read. indexOfMulti could mean

• You're searching for any one of multiple values.
• You're searching for all occurrences of a value (less likely -- might be indicesOf or findAll).
• You're searching for the first occurrence of a sequence.

I'd name this something like find, findSequence, findSubstring. I'd also rename searchElements to something like needle, targetSequence.

You have two different efficiency issues here.

First, if this code is running in an implementation without tail-call optimization (I can't tell if any do, much less whether it's common), your memory usage may blow up whenever the first part of needle is common in your haystack but the full needle isn't found, because you'll blow up the stack. Better to implement this non-recursively.

Second, you've chosen the naive string search algorithm (see http://en.wikipedia.org/wiki/String_searching_algorithm). It will work fine when needle and haystack are small, or when prefixes of needle are rare in haystack, but it will be quite slow on the following example:

haystack = "aaaaaaaaaaaaaaaaaaaaab";
needle = "aaaab";
haystack.findSequence(needle);


You'd be better off selecting one of the other algorithms in that wikipedia article; a good choice is Boyer-Moore.

-