[n8schatten]

On which parts do you need the tips?
Binary search? Comparing the strings? ...?

First tip: Don't use parallel arrays ;-)
Create a class storing a username and a password (you may want to have a look at macosxnerd101's tutorial: Moving Away From Parallel Arrays).

[n8schatten]

Well, the API of String.compareTo(String) clearly states:

Quote

Compares two strings lexicographically.

(see API for details).

Besides the comparisson using compareTo instead of <, > or == the implementation is the same as with int.

[g00se]

As has been said already, using parallel arrays is a BAD idea, and a username/password combo, is ONE piece of data.

The array needs to be already sorted in order to use a binary search. You can then use Arrays.binarySearch

[g00se]

As i mentioned above, you can use Arrays.binarySearch

public boolean valid(String username, String password) {
	int ix = -1;
	return ((ix = Arrays.binarySearch(users, username)) > -1 && passwords[ix].equals(password);
}

[baavgai]

Here's your linear, slightly rewritten:

public boolean checkPwd(String user, String password) {
	if (user == null || password != null) { return false; }
	// evil gloval parallel arrays
	if (users==null || users.length==0) { return false; }
	if (passwords==null || passwords.length==0) { return false; }
	// because if they're not equal, they're useless
	if (users.length!=passwords.length) { return false; }
	
	for (int i=0; i<users.length; i++) {
		if (users[i].equals(user)) { return passwords[i].equals(password); }
	}
	
	return false;
}

This is Java, let's make some classes:

abstract class PasswordCheckerBase {
	protected static final int NOT_FOUND = -1;
	protected String [] users, passwords;
	
	public abstract int findUser(String user);
	
	public PasswordCheckerBase(String [] users, String [] passwords) {
		if (checkValidArrays(users, passwords)) {
			this.users = users;
			this.passwords = passwords;
		}
	}
	
	protected boolean checkValidArrays(String [] users, String [] passwords) {
		if (users==null || users.length==0) { return false; }
		if (passwords==null || passwords.length==0) { return false; }
		if (users.length!=passwords.length) { return false; }
		return true;
	}
	
	protected boolean isValid() { return users!=null; }
	
	protected boolean isValid(String user, String password) {
		return isValid() && user != null && password != null;
	}
	
	
	public int getSize() { return isValid() ? users.length : 0; }
	
	public boolean checkPwd(String user, String password) {
		if (isValid(user, password)) {
			int index = findUser(user);
			if (index!=NOT_FOUND) { return passwords[index].equals(password); }
		}
		return false;
	}
}

class PasswordCheckerLinear extends PasswordCheckerBase {
	public PasswordCheckerLinear(String [] users, String [] passwords) { super(users, passwords); }
	public int findUser(String user) {
		if (isValid(user, password)) {
			int size = getSize();
			for (int i=0; i<size; i++) {
				if (getUser(i).equals(user)) { return i; }
			}
		}
		return NOT_FOUND;
	}
}

You're only really searching on one element; user. Check binary shouldn't be too hard from there:

class PasswordCheckerBinary extends PasswordCheckerBase {
	public PasswordCheckerLinear(String [] users, String [] passwords) { 
		if (checkValidArrays(users, passwords) && checkOrdered(users)) {
			this.users = users;
			this.passwords = passwords;
		}
	}
	
	private boolean checkOrdered(String [] users) { /* your code here */ }
	
	public int findUser(String user) { /* your code here */ }
}

Hope this helps.