How Can I Check Through an Array Efficiently? (Java)

Question

Scanner input = new Scanner(System.in);
String[] no = {"bob", "john", "marty", "someoneelse",};

System.out.println("What is your name? ");
String check = input.nextLine();

if(check ~= "bob" && check ~= "john" ETCETCETC){
    System.out.println("Welcome!");
}else{
    System.out.println("Error.");
}

I wrote ETCETC because it's obvious what I intend to put there.

My question is if there is a way I can check through that array without listing all of the names like that, because otherwise it would be inefficient code.

Ugh, wrong syntax. In another programming language ~= used to mean not equal to. How do you write that in Java? — Code123, Jul 19 '15 at 23:51
Most efficient will be to not use arrays at all. Arrays will give you linear complexity meaning longer the array longer the processing time. Hash on the other hand will give you constant time meaning same response time every time. — Shahzeb, Jul 20 '15 at 00:02
Something like ` Set no = new HashSet(); no.add("bob"); no.add("john"); no.add("marty"); no.add("someoneelse"); System.out.println("What is your name? "); String check = input.nextLine(); String message = "Welcome!"; if(!no.contains(check)){ message = "Error."; } System.out.println(message);` — Shahzeb, Jul 20 '15 at 00:02
@Shahzeb *Arrays will give you linear complexity* This is not entirely true. If your array is ordered, you can achieve O(log(n)) complexity with binary search. Not everything about arrays is bad :) — Turing85, Jul 20 '15 at 00:09
@Turing85 Totally agree good point. Hashing would still be better due to constant time. Overkill here ? may be . — Shahzeb, Jul 20 '15 at 00:14
@M.Shaw [Never use `==` or `!=` in conjunction with `String`s](http://stackoverflow.com/questions/767372/java-string-equals-versus) — Turing85, Jul 20 '15 at 00:15

pb2q · Answer 1 · 2015-07-19T23:53:26.653

4

It's not necessarily more efficient than iterating all the values that you want to check against, but you can do this with less code.

Convert your choices to an ArrayList and use ArrayList.contains:

if (Arrays.asList(no).contains(check))
    System.out.println("Welcome!");

Or, to check if the value doesn't exist in your list:

if (!Arrays.asList(no).contains(check))
    System.out.println("Error!");

edited Jul 19 '15 at 23:53

answered Jul 19 '15 at 23:46

pb2q

58,613
19
146
147

How would I write does not contain? – Code123 Jul 19 '15 at 23:52
1

@Code123 Negate the result. `!list.contain(check)`. It is obvious that either a list contains and object or it doesn't. – M. Shaw Jul 19 '15 at 23:53

score 2 · Answer 2 · edited May 23 '17 at 12:29

If you do not want to transform your array no into a List like pb2q proposed or in a TreeSet like jbx proposed, you can always use a foreach loop:

boolean found = false;
for (String n : no) {
    if (n.equals(check)) {
        found = true;
        break;
    }
}

if (found) {
    System.out.println("Welcome, " + check + "!");
} else {
    System.out.println("Error.");
}

This solution has the obvious downside that the time to find an element is O(n) (worst case) whereas the TreeSet (which is a Red-Black-Tree) guarantees O(log(n)). I am not sure what the time complexity for different Lists is. For ArrayList, it seems to be O(n) as well.

Sidenote on your code: If ~= is meant to be !=, you will be in a hell of a lot of troube. Read this to avoid confusion and critical bugs.

This won't work. What if they input Bob, and the foreach loop set found to false because "someoneelse" was the last choice? — Code123, Jul 21 '15 at 02:56
@Code123 the `foreach` loop does not set `found` to `false`, only to `true`. — Turing85, Jul 21 '15 at 07:47

jbx · Answer 3 · 2015-07-20T00:07:18.443

1

In order to get an efficient implementation you should use a different data structure. Instead of an array you should use something which is backed by a binary search tree. Then searching through it becomes O(log n), which is faster than checking each entry.

You can simply put your array into a TreeSet as follows:

Set<String> set = new TreeSet<String>(Arrays.asList(no));

Or better still, just populate them in the TreeSet in the first place, rather than an array.

Then to check if the string you want is not in the Set you just do:

if (!set.contains(check)) { ...

Obviously this is only useful if you need to do this check multiple times in your program, as you are still going through the list once to put them in the TreeSet.

There are other set implementations you could use too (like HashSet as Shahzeb suggested, which is even faster because its backed by a hash table) depending on the size of the array and operations you need to do on it apart from this specific search.

edited Jul 20 '15 at 00:07

answered Jul 19 '15 at 23:53

jbx

21,365
18
90
144

Could someone explain the downvote? I do not see anything wrong with this answer. – Turing85 Jul 19 '15 at 23:57
Just curious as to why you are using `TreeSet` instead of `Hashset` ? – Shahzeb Jul 20 '15 at 00:19
Not sure about what the OP is doing with the array, its size, where is it coming from, etc., so can't really say what is ideal here. In isolation and assuming a reasonable amount of elements, a `HashSet` is best. Good to know both alternatives and the concepts behind both ideas. – jbx Jul 20 '15 at 00:36

score 1 · Answer 4 · answered Jul 20 '15 at 00:18

1

This can be done in O(sqrt n) using Grovers Algorithm. I leave finding a quantum JVM as an exercise for the reader.

answered Jul 20 '15 at 00:18

emory

10,725
2
30
58

1

True, but sadly this is a probabilistic procedure =/ – Turing85 Jul 20 '15 at 00:19
1

@Shahzeb the problem is **finding** it. It is really, really tiny. And then.. one must be careful to not lose it again. [It is pretty much the same with the Higgs Boson](http://www.explainxkcd.com/wiki/index.php/1437:_Higgs_Boson). – Turing85 Jul 20 '15 at 00:22

How Can I Check Through an Array Efficiently? (Java)

4 Answers4