Java Search an array for a matching string

Question

how can I optimize the following:

final String[] longStringArray = {"1","2","3".....,"9999999"};
String searchingFor = "9999998"
for(String s : longStringArray)
    {
        if(searchingFor.equals(s))
        {
            //After 9999998 iterations finally found it
            // Do the rest of stuff here (not relevant to the string/array)
        }
    }

NOTE: The longStringArray is only searched once per runtime & is not sorted & is different every other time I run the program.

Im sure there is a way to improve the worst case performance here, but I cant seem to find it...

P.S. Also would appreciate a solution, where string searchingFor does not exist in the array longStringArray.

Thank you.

Answer 1

Well, if you have to use an array, and you don't know if it's sorted, and you're only going to do one lookup, it's always going to be an O(N) operation. There's nothing you can do about that, because any optimization step would be at least O(N) to start with - e.g. populating a set or sorting the array.

Other options though:

• If the array is sorted, you could perform a binary search. This will turn each lookup into an O(log N) operation.
• If you're going to do more than one search, consider using a HashSet<String>. This will turn each lookup into an O(1) operation (assuming few collisions).

Answer 2

import org.apache.commons.lang.ArrayUtils;
ArrayUtils.indexOf(array, string);

ArrayUtils documentation

Answer 3

You can create a second array with the hash codes of the string and binary search on that.

You will have to sort the hash array and move the elements of the original array accordingly. This way you will end up with extremely fast searching capabilities but it's going to be kept ordered, so inserting new elements takes resources.

The most optimal would be implementing a binary tree or a B-tree, if you have really so much data and you have to handle inserts it's worth it.

Answer 4

Arrays.asList(longStringArray).contains(searchingFor)