CODEWITHSUNDEEP
javaarraylist
Beppi's
Beppi's

Reputation: 2129

find in ArrayList<String>

I have this.

private ArrayList<String> words;

It's a dictionary, so the words are already sorted. By old study I know that a binomial search should be really very very quick, I suppose that Java already implements what is necessary.

So, what is the most efficient way of finding if a certain string exists inside a sorted ArrayList ? Or should I use a different type?

Thank you.

Upvotes: 1

Views: 204

Answers (4)

Mark Byers
Mark Byers

Reputation: 839154

Or should I use a different type?

Try using a HashSet<String> instead. Its contains method has O(1) lookup assuming that there are not too many hash collisions. From the documentation:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

A binary search on a sorted ArrayList is only O(log n). This is still very fast, but it is not as fast as using a HashSet.

Upvotes: 8

Grambot
Grambot

Reputation: 4523

If you're going to be doing binary searches I would suggest you reorganize your data into a Binary Search Tree

ArrayLists are often used for sequential operations and random access. If you're going to be doing a search and want the fastest lookup its best to organize your data from the get go. This also has the advantage of facilitating faster inserts/removals and all other operations you'd be hoping to accomplish in the fastest possible time.

There are tons of guides on google and elsewhere to get you started.

Upvotes: 1

fo_x86
fo_x86

Reputation: 2623

A binary search will be the fastest in a sorted array. Testing for existence can be done in constant time if you are using a hash set.

Upvotes: 3

Will
Will

Reputation: 6286

Depends how many times you're going to try and find a specific string. You might want to try a HashMap<String, String> as this will remain fast as the map grows.

Upvotes: 2

Related Questions