Array.binarySearch returning wrong data

Question

I am trying to validate password and username using array and the array.BinarySearch function. The first two user names in the array: bradley and john are returning the correct position using the function 0 and 1. However when I try to validate the last two strings in the array jim and clarke, the binarySearch function returns the username is located at position -2 in the array both times which is causing validation to fail. Any ideas?

 String[] names = {"bradley","john","jim","clarke"};
    String[] passwords = {"password","password","test","test"};
    int pos = Arrays.binarySearch(names, uname);
                    System.out.println("Found you in array:" + uname + "here:" + pos);
                    if(pos >= 0)
                    {   
                        System.out.println("Validation password for:" + uname);
                        if(passwords[pos].equals(pword) && !loggedOn[pos])
                        {
    }

Tomasz Nurkiewicz · Accepted Answer · 2012-12-06 07:39:56Z

7

Your names array is not sorted:

String[] names = {"bradley","john","jim","clarke"};

which is a requirement of binarySearch() (and binary searching algorithm in general):

The range must be sorted into ascending order

Sort it first and it'll work like a charm:

String[] names = {"bradley","clarke","jim","john"};

edited Dec 6, 2012 at 7:39

answered Dec 5, 2012 at 21:04

Tomasz Nurkiewicz

342k72 gold badges713 silver badges680 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Joop Eggen Over a year ago

Binary search requires the values to be sorted so one can split an array range in the middle and decide on the middel value which half tobsplit further with.

Bradley Over a year ago

Surely this will affect the validation of my password field then as it looks for the corresponding position in the password array which wont be the same if its sorted?

jonhopkins Over a year ago

If you implement a manual sorting algorithm instead of a built-in, then you can swap the positions of the password array whenever you swap positions in the name array

Tomasz Nurkiewicz Over a year ago

@Bradley: of course, positions in passwords need to be in sync with names array. Which is the reason why you should rather have a custom User object with name and password fields. You'll also need a custom Comparator<User>. That being said, you should consider using Map from user name to password.

Ivan · Accepted Answer · 2012-12-05 21:06:32Z

2

A binary search requires the array to be sorted before hand. You can either list the names in order, or perform the sorting yourself. You can use Arrays.sort(names) to sort the array of names.

answered Dec 5, 2012 at 21:06

Ivan

10.4k12 gold badges49 silver badges79 bronze badges

1 Comment

Vamsi Pavan Mahesh Over a year ago

it does merge sort internally ?

Collectives™ on Stack Overflow

Array.binarySearch returning wrong data

2 Answers 2

4 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related