CODEWITHSUNDEEP
javaarraysstringperformancealgorithm
PeakGen
PeakGen

Reputation: 22995

Searching for a particular String in an array

I would like to know what is the fastest way / algorithm of checking for the existence of a word in a String array. For an example, if I have a String array with 10,000 elements, I would like to know whether it has the word "Human". I can sort the array, no problem.

However, binary search (Arrays.binarySearch()) is not allowed. Other collection types like HashSet, HashMap and ArrayList are not allowed too.

Is there any proven algorithm for this? Or any other method? The way of searching should be really really fast.

Upvotes: 3

Views: 132

Answers (3)

Niklas B.
Niklas B.

Reputation: 95278

Build a trie out of the array. It can be built in linear time (assuming a constant size alphabet). Then you can query in linear time as well (time proportional to the query word length). Both preprocessing and query time are asymptotically optimal.

Upvotes: 1

Aseem Goyal
Aseem Goyal

Reputation: 2723

For fastest performance you have to use hashing .
You can use rolling hash .
It ensures lesser number of collisions . 

hash = [0]*base^(n-1) + [1]*base^(n-2) + ... + [n-1]

where base is a prime number , say 31 .

You need to take modulo also , so integer range is not exceeded , by a prime number .

Time complexity : O(number of characters) considering multiplication and modulo O(1) operation .

A very good explaination is given here : Fast implementation of Rolling hash

Upvotes: 1

Vilen
Vilen

Reputation: 5061

the fastest way you can sort will result in O(nLogn) complexity so if you are looking for particular word in unordered data just scan the array with single for cycle, that will cost you O(n)

Upvotes: 2

Related Questions