Find a list of objects in an array with JavaScript

Question

Having an array of objects, such as numbers, what would be the most optimal (Memory and CPU efficiency) way if finding a sub group of objects?

As an example:

demoArray = [1,2,3,4,5,6,7]

Finding [3,4,5] would return 2, while looking for 60 would return -1. The function must allow for wrapping, so finding [6,7,1,2] would return 5

I have a current working solution, but I'd like to know if it could be optimized in any way.

var arr = [
  1,
  5,2,6,8,2,
  3,4,3,10,9,
  1,5,7,10,3,
  5,6,2,3,8,
  9,1]
var idx = -1
var group = []
var groupSize = 0

function findIndexOfGroup(g){
  group = g
  groupSize = g.length
  var beginIndex = -2
  
  while(beginIndex === -2){
    beginIndex = get()
  }
  
  return beginIndex
}

function get(){
    idx = arr.indexOf(group[0], idx+1);
    
    if(idx === -1 || groupSize === 1){
      return idx;
    }
    var prevIdx = idx
    
    for(var i = 1; i < groupSize; i++){
      idx++
      
      if(arr[getIdx(idx)] !== group[i]){
        idx = prevIdx
        break
      }
      
      if(i === groupSize - 1){
        return idx - groupSize + 1
      }
    }
    return -2
}

function getIdx(idx){
  if(idx >= arr.length){
    return idx - arr.length
  }
  return idx
}

console.log(findIndexOfGroup([4,3,10])) // Normal
console.log(findIndexOfGroup([9,1,1,5])) // Wrapping

Answer 1

You could first get the index of the first element of the search array.

Then loop while index !== -1 and check all elements in the search array with the elements in the base array. For checking outside of the range of the array use the reminder operator %.

Return index if all elements are equal.

If not get a new index with indexOf and an incremented start value.

Array#every breaks the iteration if the callback returns false.

function find(search, array) {
    var index = array.indexOf(search[0]);

    while (index !== -1) {
        if (search.every(function (a, i) { return a === array[(index + i) % array.length]; })) {
            return index;
        }
        index = array.indexOf(search[0], index + 1);
    }
    return -1;
}

console.log(find([3, 4, 5], [1, 2, 3, 4, 5, 6, 7]));          //  2
console.log(find([6, 7, 1, 2], [1, 2, 3, 4, 5, 6, 7]));       //  5
console.log(find([60], [1, 2, 3, 4, 5, 6, 7]));               // -1
console.log(find([3, 4, 5], [1, 2, 3, 4, 6, 7, 3, 4, 5, 9])); //  6

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

My take on the problem is to use slice() and compare each subarray of length equal to the group's length to the actual group array. Might take a bit long, but the code is short enough:

// The array to run the tests on
var arr = [
  1,
  5, 2, 6, 8, 2,
  3, 4, 3, 10, 9,
  1, 5, 7, 10, 3,
  5, 6, 2, 3, 8,
  9, 1
];
// Check arrays for equality, provided that both arrays are of the same length
function arraysEqual(array1, array2) {
  for (var i = array1.length; i--;) {
    if (array1[i] !== array2[i])
      return false;
  }
  return true;
}
// Returns the first index of a subarray matching the given group of objects
function findIndexOfGroup(array, group) {
  // Get the length of both arrays
  var arrayLength = array.length;
  var groupLength = group.length;
  // Extend array to check for wrapping
  array = array.concat(array);
  var i = 0;
  // Loop, slice, test, return if found
  while (i < arrayLength) {
    if (arraysEqual(array.slice(i, i + groupLength), group))
      return i;
    i++;
  }
  // No index found
  return -1;
}
// Tests
console.log(findIndexOfGroup(arr,[4,3,10])); // Normal
console.log(findIndexOfGroup(arr,[9,1,1,5])); // Wrapping
console.log(findIndexOfGroup(arr,[9,2,1,5])); // Not found

If the group is longer than the array, some errors might occur, but I leave it up to you to extend the method to deal with such situations.

Answer 3

i would also suggest thinking about using a library like underscore.js that has already implemented such methods or at least understand their implementation via their source code http://underscorejs.org/#contains

Answer 4

I think you should consider some of the edge conditions of input in addition to just reviewing your logic.

For example, you might consider validating both inputs as arrays. You can also bail out of the function early if the "needle" is empty or its size is greater than the "haystack" array size.

I also think you can pre-prepare your haystack array to deal with the looping back to the beginning of the array.

Finally, you can leverage the Array.findIndex() method as the means to iterate the haystack the seek out the first index that meets your match criteria. This basically means you can encapsulate your comparison logic in the callback to this function.

Putting it together might yield something like:

findSubArrayIndex(needle, haystack) {
    // check for valid input types
    if (!Array.isArray(needle) || (!Array.isArray(haystack)) {
        throw new TypeError('Feed me arrays!');
    }
    var needleLen = needle.length;
    var haystackLen = haystack.length;
    // if needle is empty or is longer than haystack, bail out early
    if (needleLen === 0 || needleLen > haystackLen) return -1;     
    // modify haystack to allow for loop condition
    var searchStack = haystack.concat( haystack.slice(0, needleLen - 1) );
    // search for indexMatch
    return haystack.findIndex(
        (val, idx) => {
            var needleIdx = 0
            while (needleIdx < needle.length) {                
                if (searchStack[idx] !== needle[needleIdx]) return false;
                needleIdx++;
                idx++;
            }
            return true;
        }
    );
}