By Mike Sickler


2009-07-15 00:03:21 8 Comments

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?

25 comments

@camickr 2009-07-15 00:04:49

Arrays.asList(yourArray).contains(yourValue)

Warning: this doesn't work for arrays of primitives (see the comments).


Since you can now use Streams.

String[] values = {"AB","BC","CD","AE"};
boolean contains = Arrays.stream(values).anyMatch("s"::equals);

To check whether an array of int, double or long contains a value use IntStream, DoubleStream or LongStream respectively.

Example

int[] a = {1,2,3,4};
boolean contains = IntStream.of(a).anyMatch(x -> x == 4);

@Thomas Owens 2009-07-15 00:06:07

I am somewhat curious as to the performance of this versus the searching functions in the Arrays class versus iterating over an array and using an equals() function or == for primitives.

@Steve Kuo 2009-07-15 00:07:56

They would both be a linear search.

@Uri 2009-07-15 00:09:05

@Thomas: I think that asList() might actually allocate a new object that delegates to the existing array, so you are paying the allocation cost. The list is backed by the array so the elements themselves shoudln't be reallocated.

@Joey 2009-07-15 00:09:07

You don't lose much, as asList() returns an ArrayList which has an array at its heart. The constructor will just change a reference so that's not much work to be done there. And contains()/indexOf() will iterate and use equals(). For primitives you should be better off coding it yourself, though. For Strings or other classes, the difference will not be noticeable.

@Tom Hawtin - tackline 2009-07-15 01:05:34

The Array.asList method is very fast for arrays of primitives. ;)

@Nyerguds 2010-11-13 13:15:59

Odd, NetBeans claims that 'Arrays.asList(holidays)' for an 'int[] holidays' returns a 'list<int[]>', and not a 'list<int>'. It just contains one single element. Meaning the Contains doesn't work since it just has one element; the int array.

@Stas Jaro 2011-06-10 16:43:28

that method is about 3 times slower than a basic for search loop

@CromTheDestroyer 2011-06-14 16:51:20

Nyerguds: indeed, this does not work for primitives. In java primitive types can't be generic. asList is declared as <T> List<T> asList(T...). When you pass an int[] into it, the compiler infers T=int[] because it can't infer T=int, because primitives can't be generic.

@TWiStErRob 2012-10-17 09:16:12

@Joey just a side note, it's an ArrayList, but not java.util.ArrayList as you expect, the real class returned is: java.util.Arrays.ArrayList<E> defined as: public class java.util.Arrays {private static class ArrayList<E> ... {}}.

@Joey 2012-10-17 10:52:44

Eek. Any reason why it is another ArrayList? o.O

@Simon Lehmann 2013-07-18 17:34:35

@Јοеу Because it is not a "normal" ArrayList, Arrays.asList(T...) "returns a fixed-size list backed by the specified array." Arrays.ArrayList is just a "thin" List-wrapper around an existing array. Most importantly, you cannot add or remove elements, because it does not allocate it's own array, but directly uses the original. This makes it very cheap to use, as no copying has to be done, it just stores a reference to the original array. So don't be afraid to use Arrays.asList(T...), it is not expensive.

@Geek 2013-08-30 06:19:36

@Joey you wrote "The constructor will just change a reference so that's not much work to be done there.". which constructor?

@camickr 2013-12-07 04:31:54

@Loc, totally agree, I questioned all the up votes 2 years ago when it had 75. There really should be a limit of maybe 10 on any answer. The answer should not be used in a popularity contest, only to indicate that it is an answer the OP should consider to solve the given question.

@fool4jesus 2014-04-21 14:44:45

What's the problem with the upvotes? It saves some people time, and the more curious read the comments and learn more and so make better decisions in the future. To me, that's a successful answer.

@camickr 2014-04-21 15:04:13

@fool4jesus, this is my answer. Read my comment from above. There is no way that any answer is that good. How does a question with 700 up votes versus one with 10 up votes save people "more" time? You only need a few up votes to indicate to anybody reading the question that this answer should be considered.

@fool4jesus 2014-04-22 00:20:03

I did read your comment (as I suggested people should :-). I just don't agree. In my view, the number of upvotes can indicate the excellence of the answer, but perhaps even more the frequency of the question. I myself have been programming in java for many years, but I don't keep track of all the latest additions to the language and wanted a quick sanity check as to whether there were any better ways to do this commonly-needed function. Would you feel better if I took back my upvote?

@Jack 2014-10-08 10:27:37

This method will not work with primitives! I found only found this out after I was trying to do a similar thing with an array of integers.

@Stijn de Witt 2014-11-10 13:41:39

@fool4jesus "the number of upvotes can indicate the excellence of the answer, but perhaps even more the frequency of the question." Agreed! I actually think the score somehow translates into Google search ranking even. Thus, good answers to common questions will be high in the rankings. Sounds good to me!

@user4229245 2015-05-02 15:15:54

I'm sorry, but it's a good answer only for the particular example where the array is small. But as a general purpose solution? Converting an array to a collection just so you can use that collection to peruse itself and tell you if something exists in it? Terrible.

@Peter Cordes 2015-09-11 09:54:24

@tgm1024: as others explained in comments above yours, this is just a thin wrapper that doesn't do any copying. stackoverflow.com/questions/1128723/…

@user4229245 2015-09-11 13:05:23

@PeterCordes, it's not about copying. That "thin wrapper" is no thin wrapper----it's a method call for every single access. For really large arrays, you are always best to leave it be and let the compiler supply the access code. Really, it's not a great general purpose solution, if part of the definition of "general purpose" includes the likelihood of large datasets already in array form.

@Peter Cordes 2015-09-11 13:36:32

@tgm1024: I thought JVMs were pretty good about optimizing away trivial method calls that just return A[i] or something. It should be easy compared to most compiler optimizations, and also really effective, since it comes up a lot.

@user4229245 2015-09-11 13:52:26

@PeterCordes, well, I'll leave it here then, because whatever optimizations happen with collections, you'll likely exceed that with arrays, unless the compiler can manage (ptr++) style optimizations based upon collection hints. But be careful with micro-benchmarks. They are very very difficult to do properly with Java. In any case, it's not about copying data.

@Si8 2016-04-09 23:09:44

What about a string instead of int?

@Gilberto Ibarra 2016-06-30 16:02:10

For primitives we cand o somthing like this: public Integer keyCodes[] = { KeyEvent.KEYCODE_0};

@Salah Alshaal 2016-07-07 07:01:18

This produced java.lang.NoClassDefFoundError: IntStream using Java8 on Android

@Christophe Weis 2017-03-03 07:29:27

Take care when using an array of strings, they should be compared with String.equals method not == !

@Asqiir 2018-04-21 13:10:56

Just of curiosity: how does contains check, whether the array contains it? Does it use equals or ==?

@Akhil babu K 2018-09-21 17:16:22

If you don't want it to be case sensitive

Arrays.stream(VALUES).anyMatch(s::equalsIgnoreCase);

@WIll 2015-04-30 02:57:07

Arrays.asList() -> then calling the contains() method will always work, but a search algorithm is much better since you don't need to create a lightweight list wrapper around the array, which is what Arrays.asList() does.

public boolean findString(String[] strings, String desired){
   for (String str : strings){
       if (desired.equals(str)) {
           return true;
       }
   }
   return false; //if we get here… there is no desired String, return false.
}

@Patrick Parker 2018-09-08 06:44:24

Arrays.asList is not O(n). It's just a lightweight wrapper. Have a look at the implementation.

@mandy1339 2018-05-17 19:37:40

Create a boolean initially set to false. Run a loop to check every value in the array and compare to the value you are checking against. If you ever get a match, set boolean to true and stop the looping. Then assert that the boolean is true.

@Christian Giménez 2014-12-14 21:49:24

One possible solution:

import java.util.Arrays;
import java.util.List;

public class ArrayContainsElement {
  public static final List<String> VALUES = Arrays.asList("AB", "BC", "CD", "AE");

  public static void main(String args[]) {

      if (VALUES.contains("AB")) {
          System.out.println("Contains");
      } else {
          System.out.println("Not contains");
      }
  }
}

@Mr.G 2013-12-07 04:19:58

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");
}

@SubbaRao Boddu 2014-06-05 10:19:26

Check this

String[] VALUES = new String[] {"AB","BC","CD","AE"};
String s;

for(int i=0; i< VALUES.length ; i++)
{
    if ( VALUES[i].equals(s) )
    { 
        // do your stuff
    } 
    else{    
        //do your stuff
    }
}

@CrazedCoder 2016-03-30 01:01:15

This still works, although less effecient

@Dukeling 2018-01-04 12:42:24

This doesn't work - it will enter the else for every item that doesn't match (so if you're looking for "AB" in that array, it will go there 3 times, since 3 of the values aren't "AB").

@Sireesh Yarlagadda 2014-05-07 19:14:42

Four Different Ways to Check If an Array Contains a Value

1) Using List:

public static boolean useList(String[] arr, String targetValue) {
    return Arrays.asList(arr).contains(targetValue);
}

2) Using Set:

public static boolean useSet(String[] arr, String targetValue) {
    Set<String> set = new HashSet<String>(Arrays.asList(arr));
    return set.contains(targetValue);
}

3) Using a simple loop:

public static boolean useLoop(String[] arr, String targetValue) {
    for (String s: arr) {
        if (s.equals(targetValue))
            return true;
    }
    return false;
}

4) Using Arrays.binarySearch():

The code below is wrong, it is listed here for completeness. binarySearch() can ONLY be used on sorted arrays. You will find the result is weird below. This is the best option when array is sorted.

public static boolean binarySearch(String[] arr, String targetValue) {  
            int a = Arrays.binarySearch(arr, targetValue);
            return a > 0;
        }

Quick Example:

String testValue="test";
String newValueNotInList="newValue";
String[] valueArray = { "this", "is", "java" , "test" };
Arrays.asList(valueArray).contains(testValue); // returns true
Arrays.asList(valueArray).contains(newValueNotInList); // returns false

@Will Sherwood 2015-03-27 01:33:39

your binary search example should return a > 0;

@mbelow 2016-05-25 15:22:50

Why? I think it should return a > -1, since 0 would indicate that it is contained at the head of the array.

@Yoory N. 2017-11-30 13:08:56

The first variant with (a >= 0) was correct, just check the docs, they say "Note that this guarantees that the return value will be >= 0 if and only if the key is found".

@Thomas Owens 2009-07-15 00:05:00

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.

@Thomas Owens 2009-07-15 00:06:44

You can use the sort functions in the same class to accomplish that...I should add that to my answer.

@Joey 2009-07-15 00:10:56

Will probably cost more than the asList().contains() approach, then, I think. Unless you need to do that check very often (but if it's just a static list of values that can be sorted to begin with, to be fair).

@Thomas Owens 2009-07-15 00:13:48

True. There are a lot of variables as to which would be the most effective. It's good to have options though.

@AHH 2017-07-31 07:07:19

Could you please show us how this can be done?

@O.O.Balance 2018-01-14 00:11:47

Some code that does this here: stackoverflow.com/a/48242328/9131078

@arunwithasmile 2018-02-14 09:51:19

Sorting a whole array for a purpose of a search is expensive. We can use the same CPU time for the liner search itself. I prefer binary search on a collection which is already constructed in sorted order beforehand.

@Intracer 2011-05-31 13:17:29

You can use ArrayUtils.contains from Apache Commons Lang

public static boolean contains(Object[] array, Object objectToFind)

Note that this method returns false if the passed array is null.

There are also methods available for primitive arrays of all kinds.

Example:

String[] fieldsToInclude = { "id", "name", "location" };

if ( ArrayUtils.contains( fieldsToInclude, "id" ) ) {
    // Do some stuff.
}

@max4ever 2012-07-26 09:49:24

300kb library for 78kb android application, not always good

@Jason 2012-12-07 17:48:11

@max4ever I agree, but this is still better then "rolling your own" and easier to read then the raw java way.

@slamborne 2014-01-31 02:39:16

@GuiSim 2014-04-22 19:30:57

@max4ever Sometimes you already have this library included (for other reasons) and it is a perfectly valid answer. I was looking for this and I already depend on Apache Commons Lang. Thanks for this answer.

@Buffalo 2015-03-09 11:59:10

Or you could just copy the method (and depedencies if there are any).

@Marcel 2016-02-23 15:19:19

This is best way if you already have the Apache Commons lang in your Project. If you dont have it. You have to write your one Method.

@Kenyakorn Ketsombut 2016-08-12 13:11:56

@max4ever Most android apps are minimalized by Proguard, putting only the classes and functions you need into your app. That makes it equal to roll your own, or copy the source of the apache thing. And whoever doesn't use that minimalization doesn't need to complain about 700kb or 78kb :)

@Josh Detwiler 2017-06-26 17:52:24

Sometimes we shoot down mosquitoes with lasers. Nothing wrong with that ;)

@Andrew 2018-06-25 14:38:07

Thanks. One of the nice things about this solution, as compared with the others, is that it should be perfectly readable to anyone, e.g. if value is in some range of values do A, if it's in some other range of values do B, etc. Important if you know your code will likely be maintained by someone else and making their lives easy is more important than final jar size, or speed.

@Shineed Basheer 2015-04-28 06:40:26

In Java 8 use Streams.

List<String> myList =
Arrays.asList("a1", "a2", "b1", "c2", "c1");

myList
.stream()
.filter(s -> s.startsWith("c"))
.map(String::toUpperCase)
.sorted()
.forEach(System.out::println);

@Johannes Stadler 2015-06-10 08:41:16

Are there any advantages with this approach?

@Florian F 2018-10-26 14:36:54

It does not answer the question.

@icza 2012-09-28 07:45:46

I'm surprised no one suggested to just simply implement it by hand:

public static <T> boolean contains(final T[] array, final T v) {
    for (final T e : array)
        if (e == v || v != null && v.equals(e))
            return true;

    return false;
}

Improvement:

The v != null condition is constant inside the method, it always evaluates to the same boolean value during the method call. So if the input array is big, it is more efficient to evaluate this condition only once and we can use a simplified/faster condition inside the for loop based on the result. The improved contains() method:

public static <T> boolean contains2(final T[] array, final T v) {
    if (v == null) {
        for (final T e : array)
            if (e == null)
                return true;
    } else {
        for (final T e : array)
            if (e == v || v.equals(e))
                return true;
    }

    return false;
}

@Phoexo 2012-10-09 14:08:17

What would the performance difference be between this solution and the accepted answer?

@icza 2012-10-10 11:25:21

@Phoexo This solution is obviously faster because the accepted answer wraps the array into a list, and calls the contains() method on that list while my solution basically does what contains() only would do.

@Alastor Moody 2013-01-14 16:38:05

e == v || v != null && v.equals( e ) --- The first part of the OR statement compares e and v. The second part does the same (after checking v isn't null). Why would you have such an implementation instead of just (e==v). Could you explain this to me?

@icza 2013-01-15 08:39:10

@AlastorMoody e==v does a reference equality check which is very fast. If the same object (same by reference) is in the array, it will be found faster. If it is not the same instance, it still might be the same as claimed by the equals() method, this is what is checked if references are not the same.

@phreakhead 2013-04-02 19:30:41

Why isn't this function part of Java? No wonder people say Java is bloated... look at all the answers above this that use a bunch of libraries when all you need is a for loop. Kids these days!

@Steve Kuo 2014-01-11 00:37:26

@phreakhead It is part of Java, see Collection.contains(Object)

@Axel 2014-02-11 07:41:22

@icza If you look at the source of Arrays and ArrayList it turns out that this isn't necessarily faster than the version using Arrays.asList(...).contains(...). Overhead of creating an ArrayList is extremely small, and ArrayList.contains() uses a smarter loop (actually it uses two different loops) than the one shown above (JDK 7).

@icza 2014-02-11 14:52:57

@Axel You're right. For small arrays, this is definitely faster. For large arrays, this would be slightly slower, but would become slightly faster again if would use 2 loops based on the searched value being null or not. I've thought of these 2 loops before but left it out for simplicity.

@Skylar Saveland 2014-07-03 17:10:40

See also: potato programming.

@deworde 2015-04-01 13:42:28

-1: If you need performance, then the correct thing to do would be to encapsulate the array and cache the checks you need at assignment rather than iterating over it every time you need to do the check (and frankly, probably not to run inside a JVM). If you don't, this is wordier and less maintainable for no value.

@icza 2015-04-01 14:16:49

@deworde I kinda disagree. If you need performance regarding the contains operation, don't use arrays at all (but rather HashSet). The question was about arrays, so I showed how it can be done with arrays. And the first solution is just a simple loop, it is not complicated at all. And also if an array is already given and you have little or no choice to choose the data structure, the improved version does have value.

@user4229245 2015-05-02 15:24:38

The problem though is that conceptually you don't want to teach people to take one potentially large data structure (an array) and then convert it to another large structure (a collection) JUST so that you can have that 2nd structure peruse itself. The most important reason being that 1. it's woefully unnecessary, and 2. the actual implementation of that collection search mechanism must be regarded as opaque because it can change in future revisions of Java. It's a crummy idea on principle alone.

@Steves 2016-06-23 11:15:08

en.wikipedia.org/wiki/Loop-invariant_code_motion the "improvement" is useless, any reasonable compiler (including C1 and C2 in HotSpot) will move the null check outside the loop because the parameter is final and cannot change.

@Steves 2016-06-23 11:16:57

Moreover, you can use Objets.equals to avoid the check completely. The call will be inlined resulting in the same machine code and the same performance.

@AustrianDude 2017-07-05 15:09:17

If you don't want to throw a NPE when "array" is null, the respective part should be surrounded by a null check -> if (array != null).

@Abhishek Oza 2014-07-23 13:25:35

I am very late to join this discussion, but since my approach in solving this problem, when I faced it a few years ago, was a bit different than the other answers already posted here, I am posting that solution I used at that time, over here, in case anyone finds it usefull: (The contains() method is ArrayUtils.in() in this code.)

ObjectUtils.java

public class ObjectUtils{

/**
 * A null safe method to detect if two objects are equal.
 * @param object1
 * @param object2
 * @return true if either both objects are null, or equal, else returns false.
 */
public static boolean equals(Object object1,Object object2){
    return object1==null?object2==null:object1.equals(object2);
}

}

ArrayUtils.java

public class ArrayUtils{
/**
 * Find the index of of an object is in given array, starting from given inclusive index.
 * @param ts  Array to be searched in.
 * @param t  Object to be searched.
 * @param start  The index from where the search must start. 
 * @return Index of the given object in the array if it is there, else -1. 
 */
public static <T> int indexOf(final T[] ts, final T t, int start){
    for(int i = start; i < ts.length;++i)
        if(ObjectUtils.equals(ts[i],t))
            return i;
    return -1;
}

/**
 * Find the index of of an object is in given array, starting from 0;
 * @param ts  Array to be searched in.
 * @param t  Object to be searched.
 * @return  indexOf(ts,t,0)
 */
public static <T> int indexOf(final T[] ts, final T t){
    return indexOf(ts, t, 0);
}

/**
 * Detect if the given object is in the given array.
 * @param ts  Array to be searched in.
 * @param t  Object to be searched.
 * @return  If indexOf(ts,t) is greater than -1.
 */
public static <T> boolean in(final T[] ts, final T t){
    return indexOf(ts, t) > -1 ;
}

}

As you can see in the code above, that there are other utility methods ObjectUtils.equals() and ArrayUtils.indexOf(), that were used at other places as well.

@Uri 2009-07-15 00:05:48

If the array is not sorted, you will have to iterate over everything and make a call to equals on each.

If the array is sorted, you can do a binary search, there's one in the Arrays class.

Generally speaking, if you are going to do a lot of membership checks, you may want to store everything in a Set, not in an array.

@Thomas Owens 2009-07-15 00:10:39

Also, like I said in my answer, if you use the Arrays class, you can sort the array then perform the binary search on the newly sorted array.

@Uri 2009-07-15 00:14:59

@Thomas: I agree. Or you can just add everything into a TreeSet; same complexity. I would use the Arrays if it doesn't change (maybe save a little bit of memory locality since the references are located contiguously though the strings aren't). I would use the set if this would change over time.

@Xar E Ahmer 2014-06-25 07:24:12

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.

@Ryan 2014-04-07 19:53:57

Using a simple loop is the most efficient way of doing this.

boolean useLoop(String[] arr, String targetValue) {
    for(String s: arr){
        if(s.equals(targetValue))
            return true;
    }
    return false;
}

Courtesy to Programcreek

@Samuel Edwin Ward 2015-12-21 02:45:48

This will throw a null pointer exception if the array contains a null reference before the target value.

@WIll 2016-05-03 01:37:05

the if statement should be : if (targetValue.equals(s)) because String equals has a instanceof checker.

@assylias 2014-03-13 14:53:46

With Java 8 you can create a stream and check if any entries in the stream matches "s":

String[] values = {"AB","BC","CD","AE"};
boolean sInArray = Arrays.stream(values).anyMatch("s"::equals);

Or as a generic method:

public static <T> boolean arrayContains(T[] array, T value) {
    return Arrays.stream(array).anyMatch(value::equals);
}

@skiwi 2014-04-07 20:11:28

It's worth to also note the primitive specializations.

@mkobit 2014-12-15 17:21:18

To also add, anyMatch JavaDoc states that it "...May not evaluate the predicate on all elements if not necessary for determining the result.", so it may not need to continue processing after finding a match.

@not 2010-06-11 02:37:56

Actually , if you use HashSet as Tom Hawtin proposed you don`t need to worry about sorting and your speed is the same as with Binary Search on a presorted array, probably even faster.

It all depends on how your code is set up, obviously, but from where I stand, the order would be:

On an UNsorted array:

  1. HashSet
  2. asList
  3. sort & Binary

On a sorted array:

  1. HashSet
  2. Binary
  3. asList

So either way, HashSet ftw

@Skylar Saveland 2014-07-03 17:21:07

HashSet membership should be O(1) and binary search on a sorted collection is O(log n).

@Tom Hawtin - tackline 2009-07-15 01:13:02

Just to clear the code up to start with. We have (corrected):

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

This is a mutable static which FindBugs will tell you is very naughty. It should be private:

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

(Note, you can actually drop the new String[]; bit.)

So, reference arrays are bad, and in particular here we want a set:

private static final Set<String> VALUES = new HashSet<String>(Arrays.asList(
     new String[] {"AB","BC","CD","AE"}
));

(Paranoid people, such as myself, may feel more at ease if this was wrapped in Collections.unmodifiableSet - it could even be made public.)

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

VALUES.contains(s)

O(1).

@Drew Noakes 2011-04-25 06:54:21

Except it's O(N) to create the collection in the first place :)

@Xr. 2011-10-12 19:39:04

If it's static, it's probably going to be used quite a few times. So, the time consumed to initialise the set has good chances of being quite small compared to the cost of a lot of linear searches.

@Tom Hawtin - tackline 2012-03-07 13:23:09

Creating then the collection is going to be dominated by code loading time (which is technically O(n) but practically constant).

@Basil Bourque 2014-08-29 05:04:50

@TomHawtin-tackline Why do you say "in particular here we want a set"? What is the advantage of a Set (HashSet) in this case? Why is a "reference array" bad (by "reference array" do you mean an ArrayList backed by an array as generated by a call to Arrays.asList)?

@Tom Hawtin - tackline 2014-08-29 13:29:46

@BasilBourque The problem trying to be solved is determining whether a value is within a set of values. A Set is a very good fit. / By "reference array" I mean a Java language array of reference types. Arrays of primitives, whilst not great, are a bit short of efficient alternatives without some necessary clunky library. A later version of Java could support immutable selfless/value types, which would change things.

@nmr 2014-09-09 21:49:27

isn't this lookup actually O(log(n))

@Tom Hawtin - tackline 2014-09-09 23:51:54

@nmr A TreeSet would be O(log n). HashSets are scaled such that the mean number of elements in a bucket is roughly constant. At least for arrays up to 2^30. There may be affects from, say, hardware caches which the big-O analysis ignores. Also assumes the hash function is working effectively.

@Thorbjørn Ravn Andersen 2015-07-05 11:22:44

you have to iterate the array to create the collection. O(n). You can then argue that amortized or simiar this evens out, but you must have an O(n) step somewhere.

@Bill K 2018-09-24 20:44:31

This answer is completely right. The point most of the commenters miss is that if you were placing the objects into a collection in the first place it wouldn't be much more time than creating the array was. Just avoid using arrays unless you are absolutely sure nothing else will do (For performance purposes), using an array because you think it will be faster without testing to see if the collection is actually too slow in the first place is a perfect example of premature optimization.

@Avenger 2013-05-30 06:59:17

Use Array.BinarySearch(array,obj) for finding the given object in array or not. Ex:

if (Array.BinarySearch(str, i) > -1) -->true --exists

false --not exists

@Erik 2013-05-30 09:20:54

Note that the array needs to be sorted for this to work.

@Avenger 2013-05-31 05:37:42

There is also Array.FindIndex(array,obj) ...Anywayz thanks for the info

@ataylor 2013-06-27 20:03:05

Array.BinarySearch and Array.FindIndex are .NET methods and don't exist in Java.

@mente 2013-08-28 07:27:05

@ataylor there's Arrays.binarySearch in java. But you're right, no Arrays.findIndex

@Glen Best 2013-05-20 07:34:58

  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);
      

@Sean Owen 2013-12-30 09:53:50

Why bother with TreeSet? HashSet is faster (O(1)) and does not require ordering.

@Mark Rhodes 2011-01-20 13:58:04

Instead of using the quick array initialsation syntax to you could just initialise it as a List straight away in a similar manner using the Arrays.asList method e.g.:

public static final List<String> STRINGS = Arrays.asList("firstString", "secondString" ...., "lastString");

Then you can do (like above): STRINGS.contains("the string you want to find");

@jhodges 2012-09-19 14:13:40

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");

@camickr 2009-07-15 01:28:51

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));
    }
}

@Erik 2013-05-30 09:16:54

I don't understand this code. You sort the array 'strings' and use the same (sorted) array in both calls to binarySearch. How can that show anything except HotSpot runtime optimization? The same with the asList.contains call. You create a list from the sorted array and then does contains on it with the highest value. Of course it's going to take time. What is the meaning of this test? Not to mention being an improperly written microbenchmark

@Erik 2013-05-30 09:18:51

Also, since binary search can only be applied to a sorted set, sort and search is the only possible way to use binary search.

@Thor84no 2013-10-24 12:25:37

Sorting may have already been done for a number of other reasons, e.g., it could be sorted on init and never changed. There's use in testing search time on its own. Where this falls down however is in being a less than stellar example of microbenchmarking. Microbenchmarks are notoriously difficult to get right in Java and should for example include executing the test code enough to get hotspot optimisation before running the actual test, let alone running the actual test code more than ONCE with a timer. Example pitfalls

@Steve Kuo 2014-01-11 00:39:03

This test is flawed as it runs all 3 tests in the same JVM instance. The later tests could benefit from the earlier ones warming up the cache, JIT, etc

@dragn 2014-09-11 13:47:14

This test is actually totally unrelated. Sort & Search is linearithmic (n*log(n)) complexity, binary search is logarithmic and ArrayUtils.contains is obviously linear. It's no use to compare this solutions as they are in totally different complexity classes.

@Tom Hawtin - tackline 2009-07-15 01:18:26

ObStupidAnswer (but I think there's a lesson in here somewhere):

enum Values {
    AB, BC, CD, AE
}

try {
    Values.valueOf(s);
    return true;
} catch (IllegalArgumentException exc) {
    return false;
}

@James P. 2011-06-02 18:20:36

Exception throwing is apparently heavy but this would be a novel way of testing a value if it works. The downside is that the enum has to be defined beforehand.

Related Questions

Sponsored Content

24 Answered Questions

[SOLVED] How to get an enum value from a string value in Java?

  • 2009-03-02 22:56:34
  • Malachi
  • 913603 View
  • 1691 Score
  • 24 Answer
  • Tags:   java enums

31 Answered Questions

[SOLVED] What's the simplest way to print a Java array?

  • 2009-01-03 20:39:39
  • Alex Spurling
  • 1844548 View
  • 1642 Score
  • 31 Answer
  • Tags:   java arrays printing

76 Answered Questions

[SOLVED] Is Java "pass-by-reference" or "pass-by-value"?

43 Answered Questions

21 Answered Questions

[SOLVED] How do I declare and initialize an array in Java?

  • 2009-07-29 14:22:27
  • bestattendance
  • 3935590 View
  • 1738 Score
  • 21 Answer
  • Tags:   java arrays declare

69 Answered Questions

[SOLVED] How do I remove a particular element from an array in JavaScript?

  • 2011-04-23 22:17:18
  • Walker
  • 5306302 View
  • 6612 Score
  • 69 Answer
  • Tags:   javascript arrays

30 Answered Questions

[SOLVED] How to append something to an array?

18 Answered Questions

[SOLVED] How do I empty an array in JavaScript?

  • 2009-08-05 09:08:39
  • amir
  • 2037718 View
  • 2199 Score
  • 18 Answer
  • Tags:   javascript arrays

18 Answered Questions

[SOLVED] Determine whether an array contains a value

23 Answered Questions

[SOLVED] How do you check if a variable is an array in JavaScript?

Sponsored Content