Most efficient/faster way of checking if string belongs to array

Question

I want to find the most efficient/fastest way of checking if a string belongs in an array in both Java and JavaScript.
For example, I want to find if the string "=" belongs in the array {"+", "-", "=", "*", "/", "!"}

A way to do it in Java is(omitting the main method)

String[] symbols = {"+", "-", "=", "*", "/", "!"};
String equalTo = "=";
for(String i: symbols) {
  if(equalTo.equals(i)) {
    System.out.print(equalTo + " belongs to symbols.");
  }
}

I would like to know if there is a single method which does this work for me in either Java and JavaScript.

The reason I am asking this in both languages is that I want to see if it is easier in Java or JavaScript.

Java and Javascript are two entirely different languages, why would you need to use the exact same code for a particular problem in different languages ? — Dici, Sep 05 '15 at 09:34
Why is this question getting low votes? I am merely curious if such a function is easier in Java or JavaScript. — user41805, Sep 05 '15 at 09:40
This is a very basic algorithm, you don't care if it is "simpler" (you most certainly mean "shorter") in Java or JS, it's just a code you can write in 5 seconds in either language. — Dici, Sep 05 '15 at 09:41
possible duplicate of [Determine whether an array contains a value](http://stackoverflow.com/questions/1181575/determine-whether-an-array-contains-a-value) — Michel, Sep 05 '15 at 09:54

score 1 · Answer 1 · edited May 23 '17 at 10:26

1

Answers for your question in JavaScript: How do I check if an array includes an object in JavaScript?

E.g. If you search for full match you can use:

["=", "+", "-"].indexOf("=") // => 1

edited May 23 '17 at 10:26

Community

1
1

answered Sep 05 '15 at 09:36

zmii

4,123
3
40
64

http://stackoverflow.com/questions/558978/most-efficient-way-to-see-if-an-arraylist-contains-an-object-in-java ? – zmii Sep 05 '15 at 09:41
@zmii an `ArrayList` is not an array in Java. – bcsb1001 Sep 05 '15 at 09:50

Infima · Answer 2 · 2015-09-05T10:10:03.730

The most efficient way to see if a string is in a collection of strings, is when this collection is already hashed. For example, if you have a HashSet<String> in Java, you can just use the .contains(String) method, which runs in O(1).

If your collection is stored as a ArrayList<String> or array, it takes O(n) time to check if a string is in the collection (also with the .contains(String) method).

Turning a list or array into a set takes O(n) time, but takes longer than checking if a single element is in the list.

So, in conclusion:

If you only want to check for one element if it's in the collection, just iterate over the list that you apparently already have, and check if the element is in the list. For an array, in Java simply use Arrays.asList(symbols).contains(equalTo) and in JavaScript use symbols.contains(equalTo)
If you want to check for a lot of elements whether they are in the collection, then it's better to turn the collection into a set first. In Java, do something like
```
HashSet<String> set = new HashSet<String>();
set.addAll(Arrays.asList(symbols));
```
after which you can do set.contains(equalTo).

For JavaScript, that's a little more annoying, but the first thing off the top of my head is like this:
```
var set = Object.create(null);
for (var i in symbols) {
    set[i] = true;
}
```
Then, you can check if checkTo in set.

Sorry for long answer, but you asked for efficiency right?

An array is a collection (not Java-wise obviously, that's why I say collection instead of Collection) — Infima, Sep 05 '15 at 09:53
Also, the initialisation of `set` doesn't utilise [`HashSet(Collection extends E>)`](http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#HashSet(java.util.Collection)). Is this constructor bad practice? I don't know why it is there, then. — bcsb1001, Sep 05 '15 at 09:55
The constructor is not bad practice at all, but I often combine collections, so I prefer to see the `addAll` method as a separate step. `HashSet set = new HashSet(Arrays.asList(symbols))` is just as valid. — Infima, Sep 05 '15 at 10:09

score 0 · Accepted Answer · answered Sep 05 '15 at 09:36

0

In Java you can use Arrays.asList(yourArray).contains(yourValue). If you use jQuery you can use $.inArray(yourValue, yourArray).

answered Sep 05 '15 at 09:36

Oleksandr Zaiats

768
2
10
15

Do both functions return booleans? – user41805 Sep 05 '15 at 09:37
Expensive to create an array list for this. Expensive to rely on a library for this – Dici Sep 05 '15 at 09:39
Java contains returns boolean. inArray returns index of value in array (if contains it must be more than -1). – Oleksandr Zaiats Sep 05 '15 at 09:40
It can be expensive for memory, but not for time (if we compare this solution with simple for cycle with equals). Kritixi Lithos can use jQuery if he has already used it in project. – Oleksandr Zaiats Sep 05 '15 at 09:47
You can just iterate through the array that's the most efficient and natural way... you may want to have a one-liner, so just write a method which does the job and never think about it anymore. Why complicate things by using library methods ? Arrays are the most basic data structure – Dici Sep 05 '15 at 09:49
1

@Dici The Java code doesn't create a java.util.ArrayList, and it doesn't copy the array. `Arrays.asList(..)` just wraps the given array into a `List` backed by that array, so it's constant-time and very fast. (That's why, for instance, you can set an already-existing element in the resulting list, but you can't add an element -- because you can set an array element, but you can't add new indexes to an array.) – yshavit Sep 05 '15 at 10:30
@yshavit well that's true the overhead is tiny – Dici Sep 05 '15 at 10:33

score 0 · Answer 4 · answered Sep 05 '15 at 10:25

The "best" way to do it really depends on the number of values to match against and how often you need to do it.

If the list is long, and you do it often, you'd be better served by creating a set/map/associate-array for fast lookup, or sort the list of values and perform a binary search. In Java, that would be Set<String> or Arrays.binarySearch().

However, in your case the list is short, so a sequential search like you're doing is fine.

But in addition to that, your values are all single-character, so there is a solution that just happens to be the exact same solution for both Java and JavaScript: indexOf()

In Java:

if ("+-=*/!".indexOf(value) != -1) {
    // found
}

In JavaScript:

if ("+-=*/!".indexOf(value) != -1) {
    // found
}

Eerie, huh?

Most efficient/faster way of checking if string belongs to array

4 Answers4