0

I have an array (1000 pieces) of brands, where I would like to provide a fast search. So when I start typing ie: "m" then I should get "mammut" and "millet". The array is sorted. So does anybody know a fast solution which doesn't need to loop through the whole array? Best in javascript. Thanks

var brands = new Array("arcterix", "mammut", "millet", "ortovox", ... )

function search(brands, substring){
 // will return array of founded brands which begins on substring
}
Arwin Edward
  • 133
  • 7
  • well you have to loop through it once at least.... Than each character you can loop over the subset... – epascarello Dec 03 '18 at 13:46
  • I think you are a beginner and don't about search engines. You should use ElasicSearch : https://www.elastic.co/ or Solr: http://lucene.apache.org/solr/ or if it a basic task than you have loop as suggested by @epascarello – Aabir Hussain Dec 03 '18 at 13:49
  • @epascarello I am not sure if I need to loop it once at least because when I type for exampe "m" than I know I need to search somewhere in middle and use a binary search. Or am I wrong? – Arwin Edward Dec 03 '18 at 13:55
  • @ArwinEdward somehow you need to know where `m` is.... So yes you can do a search to figure out where the start of "m" is. ou can try it and see if it is faster than just looping. – epascarello Dec 03 '18 at 13:55
  • 1000 is not a lot... Use loop or `[].reduce`, or `[].filter`. – VisioN Dec 03 '18 at 13:57
  • @epascarello yes I know but for figuring where m is I have smaller complexity (i think O log n ) than with looping whole array (O n). I am wondering if javascript have some built functions for that, or I need to reinvent wheel once again. Aabir Hussain Elastic search is really large, I need just nice small function which can handle this search. – Arwin Edward Dec 03 '18 at 14:01
  • There is not built in functionality, only way you could make it fast is preprocess the data so it is an an object lookup instead of an array. `var words = { a: ["animal","apple"], b: [], c: [] ....}` – epascarello Dec 03 '18 at 14:09
  • 2
    As noted, you probably don't need anything fancy for your particular use case. That said, if you are interested in implementing a binary search function, see [Binary Search in JavaScript](https://stackoverflow.com/questions/22697936/binary-search-in-javascript) – benvc Dec 03 '18 at 15:19

1 Answers1

2

Try this

var brands = ["arcterix", "mammut", "millet", "ortovox"]

function search(brands, substring){
 return brands.filter( i => i.startsWith(substring) )
}

console.log(search(brands, 'm')) // ['mammut', 'millet']

This is very fast. It's almost impossible to do things faster, everything is optimized for you.

Nurbol Alpysbayev
  • 19,522
  • 3
  • 54
  • 89
  • This is indeed the best and the only proper way to do this for just 1000 items :) However, it is far from being the fastest algorithm and it is not "optimized". This algorithm works for `O(n*pLen)` where `pLen` is the length of a prefix. The main point here is that input array is sorted and therefore it can be improved by utilizing binary search. – Yeldar Kurmangaliyev Dec 03 '18 at 16:18
  • @YeldarKurmangaliyev yes, but the question feels to me like the author is quite a newbie. So I've infered that this solution is nothing more than what he needs. – Nurbol Alpysbayev Dec 03 '18 at 16:30
  • @NurbolAlpysbayev Perfect! :) – Yeldar Kurmangaliyev Dec 03 '18 at 17:38
  • @YeldarKurmangaliyev and is there a binary search library for js, or I need to implement myself? – Arwin Edward Dec 04 '18 at 11:04
  • 1
    @ArwinEdward You would have to implement it yourself, it is pretty simple algorithm, but its usage case is tricky, because you need find both left-most and right-most occurence, and then do the same recursively for all following letters. **But**...as already mentioned by Nurbol, it simply won't bring any improvement for 1000 items. No need to overengineer it. Binary search would make sense here, if you get closer to millions of items. I just corrected the statement that it is "very fast and it's almost impossible to do things faster" :) – Yeldar Kurmangaliyev Dec 04 '18 at 11:40