1

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.

4 Answers 4

8

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.

11
  • 1
    @MarkByers "on average" suggests that there must be a case where its faster than O(1). Now I'm dying to see how that would be achieved. O(log N) can be good enough in practice, especially if using a set means data need to be duplicated...
    – Durandal
    Jan 15, 2013 at 15:03
  • Thank you. Is "contains" method slower on ArrayList? That's because I also need to keep the indicization of the strings.
    – Beppi's
    Jan 15, 2013 at 15:05
  • @Durandal On average means that if there are hash collisions, it will take more than O(1). I'm not sure how any algorithm can be faster than O(1).
    – fo_x86
    Jan 15, 2013 at 15:05
  • @BeppiMenozzi Yes, it has to iterate through the entire array (O(n)) to test for existence (that is, if you don't make any assumptions about sorted-ness of the data).
    – fo_x86
    Jan 15, 2013 at 15:06
  • @fox... thanks. Anyway as I said elsewhere, I also need indicization: would HashMap<Integer, String> be a good choice, then?
    – Beppi's
    Jan 15, 2013 at 15:12
3

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.

1
  • You're welcome. If you must use a binary search, Google's Guava library already has an implementation. See com.google.common.collect.Ordering.
    – fo_x86
    Jan 15, 2013 at 15:09
2

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.

2
  • I could use HashMap<Integer, String> ; would that be faster, compared to an ArrayList, when searching?
    – Beppi's
    Jan 15, 2013 at 15:08
  • It would be faster than an array list, but no faster than a hashset. Depending on your other requirements, HashSet is probably your way to go. Sorting is when you need to retrieve more than one element, or have the array in a specific order.
    – Will
    Jan 15, 2013 at 15:20
1

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.

1
  • Not really, thanks anyway. I just wanted to look for the existance of a particular word into a sorted array of strings. I was talking about binary search because as I remember it was an optimized algorhytm for the search in a sorted array.
    – Beppi's
    Jan 15, 2013 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.