How to determine whether an array contains a parti

Question

I have a String[] with values like so:

public static final String[] VALUES = new String[] {"AB","BC","CD","AE"};

Given String s, is there a good way of testing whether VALUES contains s?

Answer 1

1. For arrays of limited length use the following (as given by camickr). This is slow for repeated checks, especially for longer arrays (linear search).

    Arrays.asList(...).contains(...)
   

2. For fast performance if you repeatedly check against a larger set of elements

   • An array is the wrong structure. Use a TreeSet and add each element to it. It sorts elements and has a fast exist() method (binary search).

   • If the elements implement Comparable & you want the TreeSet sorted accordingly:

     ElementClass.compareTo() method must be compatable with ElementClass.equals(): see Triads not showing up to fight? (Java Set missing an item)

     TreeSet myElements = new TreeSet();
     
     // Do this for each element (implementing *Comparable*)
     myElements.add(nextElement);
     
     // *Alternatively*, if an array is forceably provided from other code:
     myElements.addAll(Arrays.asList(myArray));
     

   • Otherwise, use your own Comparator:

     class MyComparator implements Comparator<ElementClass> {
          int compareTo(ElementClass element1; ElementClass element2) {
               // Your comparison of elements
               // Should be consistent with object equality
          }
     
          boolean equals(Object otherComparator) {
               // Your equality of comparators
          }
     }
     
     
     // construct TreeSet with the comparator
     TreeSet myElements = new TreeSet(new MyComparator());
     
     // Do this for each element (implementing *Comparable*)
     myElements.add(nextElement);
     

   • The payoff: check existence of some element:

     // Fast binary search through sorted elements (performance ~ log(size)):
     boolean containsElement = myElements.exists(someElement);
     

Answer 2

For what its worth I ran a test comparing the 3 suggestions for speed. I generated random integers, converted them to a String and added them to an array. I then searched for the highest possible number/string, which would be a worst case scenario for the asList().contains().

When using a 10K array size the results where:

Sort & Search   : 15
Binary Search   : 0
asList.contains : 0

When using a 100K array the results where:

Sort & Search   : 156
Binary Search   : 0
asList.contains : 32

So if the array is created in sorted order the binary search is the fastest, otherwise the asList().contains would be the way to go. If you have many searches, then it may be worthwhile to sort the array so you can use the binary search. It all depends on your application.

I would think those are the results most people would expect. Here is the test code:

import java.util.*;

public class Test
{
    public static void main(String args[])
    {
        long start = 0;
        int size = 100000;
        String[] strings = new String[size];
        Random random = new Random();


        for (int i = 0; i < size; i++)
            strings[i] = "" + random.nextInt( size );

        start = System.currentTimeMillis();
        Arrays.sort(strings);
        System.out.println(Arrays.binarySearch(strings, "" + (size - 1) ));
        System.out.println("Sort & Search : " + (System.currentTimeMillis() - start));

        start = System.currentTimeMillis();
        System.out.println(Arrays.binarySearch(strings, "" + (size - 1) ));
        System.out.println("Search        : " + (System.currentTimeMillis() - start));

        start = System.currentTimeMillis();
        System.out.println(Arrays.asList(strings).contains( "" + (size - 1) ));
        System.out.println("Contains      : " + (System.currentTimeMillis() - start));
    }
}

Answer 3

You can use the Arrays class to perform a binary search for the value. If your array is not sorted, you will have to use the sort functions in the same class to sort the array, then search through it.

Answer 4

Developers often do:

Set<String> set = new HashSet<String>(Arrays.asList(arr));
return set.contains(targetValue);

The above code works, but there is no need to convert a list to set first. Converting a list to a set requires extra time. It can as simple as:

Arrays.asList(arr).contains(targetValue);

or

   for(String s: arr){
        if(s.equals(targetValue))
            return true;
    }

return false;

The first one is more readable than the second one.

Answer 5

If you have the google collections library, Tom's answer can be simplified a lot by using ImmutableSet (http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/ImmutableSet.html)

This really removes a lot of clutter from the initialization proposed

private static final Set<String> VALUES =  ImmutableSet.of("AB","BC","CD","AE");

Answer 6

Try this:

ArrayList<Integer> arrlist = new ArrayList<Integer>(8);

// use add() method to add elements in the list
arrlist.add(20);
arrlist.add(25);
arrlist.add(10);
arrlist.add(15);

boolean retval = arrlist.contains(10);
if (retval == true) {
    System.out.println("10 is contained in the list");
}
else {
    System.out.println("10 is not contained in the list");
}