CODEWITHSUNDEEP
java
Code123
Code123

Reputation: 345

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

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.

Upvotes: 1

Views: 95

Answers (4)

emory
emory

Reputation: 10891

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

Upvotes: 1

Turing85
Turing85

Reputation: 20185

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.

Upvotes: 2

jbx
jbx

Reputation: 22128

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.

Upvotes: 1

pb2q
pb2q

Reputation: 59617

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

Upvotes: 4

Related Questions