How to code a non brutal search

Question

I'm coding a javascript snippet that searches for a match between two arrays. I know how to search it brutally (array takes a number input, searches each value of the other arrays to see if they match do this over and over again) but it is very inefficient. If anyone knows a way to search for a common value between two arrays so that it takes minimum time possible, please help me.

var 1 = ["bob", "Sophie"];
var 2 = ["Sherry", "Gerard", "Joseph"];

for(var i; i <= 1.length; i++){

switch(1[i]){

case 1[i] === 2[1]:
console.log("They match!");

break;

case 1[i] === 2[2]:
console.log("They match!");

break;

case 1[i] === 2[3]:
console.log("They match!");

break;

case default:
console.log("No matches found.");

}
}
}

PS Don mind the syntax errors, this is a "Rough draft" of the code. I put it just so that you could see what I meant.

How large will the arrays be? Instinctively I'd say it would be fastest (for larger arrays) to sort the array and then search it. — Ivan Modric, Feb 25 '17 at 21:20
@IvanModric the arrays will be pretty big, around 200 values will be stored in them on average. How can I sort arrays? — Theodore Tremblot, Feb 25 '17 at 21:44
You could google 'quicksort'. This seems to be an ok implementation, but I'm on a mobile phone at the moment so I can't properly edit the comment or check the code: https://gist.github.com/paullewis/1981455 — Ivan Modric, Feb 25 '17 at 22:00

Nina Scholz · Answer 1 · 2017-02-25T22:14:53.300

You could use a hash table and iterate the first array to create a table and then just filter the second array with a single loop.

Complexity: O(n + m)

var array1 = ["bob", "Sophie"],
    array2 = ["Sherry", "Gerard", "Joseph"],
    hash = Object.create(null),
    found;

array1.forEach(function (a) {
    hash[a] = true;
});

found = array2.filter(function (a) {
    return hash[a];
});
console.log(found);

array2.push("Sophie");
found = array2.filter(function (a) {
    return hash[a];
});
console.log(found);

ES6 with Set

var array1 = ["bob", "Sophie"],
    array2 = ["Sherry", "Gerard", "Joseph"],
    aSet = new Set(array1),
    found;

found = array2.filter(a => aSet.has(a));
console.log(found);

array2.push("Sophie");
found = array2.filter(a => aSet.has(a));
console.log(found);

... assuming that the hash lookups/inserts are O(1). In theory, they will rather by O(log(n)) — Hagen von Eitzen, Feb 25 '17 at 22:07
actually the building of the table is O(n) plus the lookup for the value. — Nina Scholz, Feb 25 '17 at 22:09

score 0 · Answer 2 · edited May 23 '17 at 11:46

If I understand correctly, you need to find common elements. Then I will go with Underscore.Js external library (as given in below snippet) or there are other solutions suggested in the following link How to find common elements only between 2 arrays in jquery

var array1 = ["bob", "Sophie"];
var array2 = ["bob", "Gerard", "Joseph"];

alert(_.intersection(array1, array2));

<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>

How to code a non brutal search

2 Answers2