8 Replies - 2628 Views - Last Post: 25 January 2011 - 03:22 AM Rate Topic: -----

#1 Guest_Exose*


Reputation:

Binary Search on two string array

Posted 24 January 2011 - 08:12 AM

Hi,

I am trying to create a binary search on two arrays:

public String[] users = {"aaa", "bbb", "ccc", "ddd", "eee", "fff", "ggg", "hhh", "iii", "jjj"};
public String[] passwords = {"aaa", "bbb", "ccc", "ddd", "eee", "fff", "ggg", "hhh", "iii", "jjj"};

I have seen few examples how to implement binary search on the int array, and it is pretty simple, however I am not sure how to implement this on the strings.

Would you be able to give me few tips?

thanks in advance
E

Is This A Good Question/Topic? 0

Replies To: Binary Search on two string array

#2 n8schatten  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 263
  • Joined: 07-December 10

Re: Binary Search on two string array

Posted 24 January 2011 - 08:19 AM

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).
Was This Post Helpful? 1
  • +
  • -

#3 Guest_Exose*


Reputation:

Re: Binary Search on two string array

Posted 24 January 2011 - 08:36 AM

I need to use parallel arrays as that a requirement of my assignment. :(

Anyway, I know what I should do in theory:
1. Array A and B have 10 elements
2. A/2, B/2
3. Now I need to take one element in my example it will be "ddd"
4. compareTo the element was is searched: if it equals; if it is lower and if it is higher. However, how to implement it, if it is a string? String is not a number, so it cant be higher or lower right?
5. if I have an array with one element and the item was not found, program should stop.
Was This Post Helpful? 0

#4 n8schatten  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 145
  • View blog
  • Posts: 263
  • Joined: 07-December 10

Re: Binary Search on two string array

Posted 24 January 2011 - 08:47 AM

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.
Was This Post Helpful? 0
  • +
  • -

#5 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2639
  • View blog
  • Posts: 11,148
  • Joined: 20-September 08

Re: Binary Search on two string array

Posted 24 January 2011 - 10:11 AM

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
Was This Post Helpful? 0
  • +
  • -

#6 Guest_Exose*


Reputation:

Re: Binary Search on two string array

Posted 24 January 2011 - 10:25 AM

ok, let me explain you a bit more:

I have a class where I have an input point:

GuessingGame:

public void one()
	{
		scan = new Scanner(System.in);
		System.out.print("What is your user name? :");
		//input point
		userNameInput = scan.next();

		System.out.print("What is your password? :");

		passwordInput = scan.next();

		LinearUserValidation validator = new LinearUserValidation();
        if (validator.checkPwd(userNameInput, passwordInput))
        	{
            	GuessingGame theGame = new GuessingGame();
            	theGame.start();
       		}
        else
        	{
            	System.out.println("Your User Name or Password is wrong, please input correct values");
            	one();
        	}


Then in LinearUserValidation class I am checking it if userName and password is good.

my Linear algorithm

public boolean checkPwd(String user, String password)
 		{
        	boolean isValid = false;

        	if (users != null && passwords != null && users.length > 0 && passwords.length > 0)
        	{
            	for (int ix = 0; ix < users.length; ix++)
            	{
                	if (users[ix].equals(user))
                	{
                    	if (passwords.length > ix)
                    	{
                        	if (passwords[ix].equals(password))
                        		{
                            		isValid = true;
                        		}
                    	}
                	}
            	}


It is working as designed and I dont have any problems with it.

Now, I want to create class where I will do the same but with binary search so...

I am not sure how to start... I have created checking for user and password:

public static int checkUsr(String [] users, String user)
	{
        int low = 0;
        int high = users.length;
        int mid;

        while( low <= high )
        {
            mid = ( low + high ) / 2;

            if( users[mid].compareTo(user) < 0 )
                low = mid + 1;
            else if( users[mid].compareTo(user) > 0 )
                high = mid - 1;
            else
                return mid;
        }

        return NOT_FOUND;     // NOT_FOUND = -1
	}

	public static int checkPwd(String [] passwords, String password)
	{
        int low = 0;
        int high = passwords.length;
        int mid;

        while( low <= high )
        {
            mid = ( low + high ) / 2;

            if( passwords[mid].compareTo(password) < 0 )
                low = mid + 1;
            else if( passwords[mid].compareTo(password) > 0 )
                high = mid - 1;
            else
                return mid;
        }

        return NOT_FOUND;     // NOT_FOUND = -1
	}


but I would like to use arguments from my main GuessingGame class and point it to the method from BinaryUserValidation class.

I am not sure how to do this
Was This Post Helpful? 0

#7 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2639
  • View blog
  • Posts: 11,148
  • Joined: 20-September 08

Re: Binary Search on two string array

Posted 24 January 2011 - 10:46 AM

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

Was This Post Helpful? 0
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5760
  • View blog
  • Posts: 12,574
  • Joined: 16-October 07

Re: Binary Search on two string array

Posted 24 January 2011 - 01:04 PM

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.
Was This Post Helpful? 0
  • +
  • -

#9 Guest_Exose*


Reputation:

Re: Binary Search on two string array

Posted 25 January 2011 - 03:22 AM

g00se... u are my HERO! :)

this code is so simple... :)

thank you very much!

thanks others for an input too! :)
Was This Post Helpful? 0

Page 1 of 1