How to search an item across many arrays efficiently?

Question

I have 3 arrays and I need to find the array where the string matches.

Eg:

var arr1 = ['apple','banana','orange'];
var arr2 = ['abc','def','ghi'];
var arr3 = ['james','joe','robert','msg'];
var search = "abc joe 12345 msg:(somecontent)";
var arr = search.split(' ');
        
    for(var i in arr){
        
        if(arr1.indexOf(arr[i]) != -1) {
          console.log('Found in arr1');
        }
        else if(arr2.indexOf(arr[i])!= -1){
          console.log('Found in arr2');
        }
        else if(arr3.indexOf(arr[i])!=-1){
          console.log('Found in arr3');
        }
        else{
          console.log('Not Found');
        }
        
    }

Is there an efficient way of doing this search when there are thousands of items in each array.

One more trouble I had with the search string is that, I need msg to be split out from the (somecontent). One thing I can do is to split that arr[3].split(":");. But the problem is msg:(somecontent) does not appear at the same position every time. So I cannot do the arr[3].split(":");. I'm searching only in 'arr'. If I do the arr[3].split(":");, I will create a new array and I won't be searching in that. I don't think I can avoid the second array.

if you can change the order of array use [binary search algorithm](http://stackoverflow.com/questions/22697936/binary-search-in-javascript) — Burak Akyıldız, May 12 '17 at 06:02
Why do you need this to be efficient? Is there an actual performance reason or is this just premature optimization? — Soviut, May 12 '17 at 06:04
@Soviut That's what I think. I need to tokenize such strings, around 40k of them, and append them to html table. — Sai Velamuri, May 12 '17 at 06:08
There is no efficient way to search a totally random array, if it's sorted or have some other characteristics then that's another story. Otherwise, there is no other way other than looking at each element one by one. — John, May 12 '17 at 06:10
@SaiVelamuri yes if you can sort the array straight you can check it in js — Burak Akyıldız, May 12 '17 at 06:11
Concerning the `split(":")` trouble. Use regular expression in split: `var arr = search.split(/ |:/);`. [Demo](https://jsfiddle.net/3pmmxhhz/) — Joe Black, May 12 '17 at 06:44

score 0 · Answer 1 · answered May 12 '17 at 06:11

0

If you think there could be too many iterations of this code (for which you need optimization), you might afford some effort on sorting and combining the data into a single array of unique values. Then use binary search.

answered May 12 '17 at 06:11

Vikas

626
1
10
22

You should improve your answer by explaining what a binary search is and give examples and links. – Soviut May 12 '17 at 06:14
If he found the index in 'unique array' then how he know what is the real index and real array ? Think there is same string in 2 different array. And there will 1 of that string in 'unique array'. It will not work – Burak Akyıldız May 12 '17 at 06:14
@Burak, The current code that he has shared does not show the index anyway. Hence his requirement will be met. – Vikas May 12 '17 at 06:17
@vikas It is not an answer for that question too 'find the array where the string matches' – Burak Akyıldız May 12 '17 at 06:19

score 0 · Answer 2 · answered May 12 '17 at 07:07

You can split your string using regex

var a = ['amy', 'john', 'dev', 'garret', 'frank', 'sean', 'happy'];
var str = 'Amy test dev msg:(car runs slowly) happy   ...';
sort(a);
// Array a will look like below
// ["amy", "dev", "frank", "garret", "happy", "john", "sean"]

Strings are sortable so you can split your array in the middle. If string in part A then keep splitting part A otherwise part B. This will quick get you the result.

function search( arr, str ) {
    while ( arr.length > 1 ) {
        var m = Math.floor( arr.length / 2 );
        if ( str >= arr[m] ) {
            arr.splice( 0, m );
        } else {
            arr.splice( m );
        }
  }

  if ( arr[0] == str ) return true;
  return false;
}

score 0 · Answer 3 · answered May 12 '17 at 13:45

The most simple, but at the same time most useful optimization is to use objects for arr1, arr2, arr3. This way you can use arr1[word] (or obj1 will be more appropriate naming now) instead of arr1.indexOf(word). In general former complexity will be O(1) (as this is a hash table) and later - O(n).

How to search an item across many arrays efficiently?

3 Answers3