I've been struggling a couple days now attempting to write this code. Basically,we have to perform a binarySearch based on the SSN of Comparable "Student" objects in a Student array. After performing the binarySearch on the SSN, the student who is associated with that SSN's first and last name should print out and the position/location of that student should print. The issue I'm having is that when I perform the binarySearch to find the location/position of the Student it always returns "-1" and not the element position of the student. Any help?
Student class
package binarySearch;
public class Student implements Comparable<Student>{
private String firstName, lastName, SSN, bankAccount;
public Student(String first, String last, String ssn, String bkacct) {
this.firstName = first;
this.lastName = last;
this.SSN = ssn;
this.bankAccount = bkacct;
}
public String getFirstName() {
return firstName;
}
public String getLastName() {
return lastName;
}
public String getSSN() {
return SSN;
}
public String getBankAccount() {
return bankAccount;
}
//toString method
public String toString() {
return "Employee: [FirstName = " + firstName + ", LastName = " + lastName + ", SSN = " + SSN + ", BankAccount = "
+ bankAccount + "]";
}
public boolean equals(Object other) {
return (lastName.equals(((Student)other).getLastName()) &&
firstName.equals(((Student)other).getFirstName())&&
SSN.equals(((Student)other).getSSN()) &&
bankAccount.equals(((Student)other).getBankAccount()));
}
//Sorting the array based on SSN
public int compareTo(Student key) {
return SSN.compareTo(key.getSSN());
}
}
where i sort my array for the binarySearch
package binarySearch;
public class ObjectBubbleSorter {
public static void bubbleSort(Comparable[] array) {
int lastPos;
int index;
Comparable temp;
for(lastPos = array.length-1; lastPos >= 0; lastPos -= 1) {
for(index = 0; index <= lastPos - 1; index+=1) {
if(array[index].compareTo(array[index+1]) > 0) {
temp = array[index];
array[index] = array[index+1];
array[index+1] = temp;
}
}
}
}
}
and where i perform my binarySearch
package binarySearch;
public class ObjectBubbleSortTest {
public static int binarySearch(Student list[], Student key) {
int low = 0;
int high = list.length - 1;
int middle = (low + high + 1)/2;
int location = -1;
while((low <= high) && (location == -1)){
if (list[middle].equals(key)) { //location current middle
location = middle;
}
else if(list[middle].compareTo(key) < 0 ) { //middle too high
high = middle - 1;
}
else {
low = middle + 1;
}
middle = (low + high + 1)/2;
}
return location;
}
public static void main(String[]args) {
Student[] student = new Student[5];
//order: First Name, Last Name, SSN, Bank_Account_Number
student[0] = new Student("Adam", "Sarrone", "1234567", "9022345");
student[1] = new Student("Ryan", "Petrowvoksi", "4345123", "0120345");
student[2] = new Student("Jenn", "Henderson", "8124512", "564214");
student[3] = new Student("Ricky", "Jean", "3512345", "612345");
student[4] = new Student("Dare", "Ogun", "421451", "198213");
System.out.println("Original array order: \n");
for (Student element : student)
System.out.print(element + "\n");
//sorting array
ObjectBubbleSorter.bubbleSort(student);
System.out.println();
System.out.println("\nSorted array order: \n");
for (Student element : student)
System.out.print(element + "\n");
System.out.println();
//creating student obj
Student student1 = new Student("Ryan", "Petrowvoksi", "4345123", "0120345");
int studentSSN = binarySearch(student, student1);
System.out.print(studentSSN);
System.out.print(student1.getFirstName() + " " + student1.getLastName() + " was found at position: " + studentSSN);
}
When i perform that binarySearch it always returns -1 and not the student element position
Change this line list[middle].compareTo(key) < 0 into list[middle].compareTo(key) > 0 inside the binarySearch while-loop.
It seems that your compareTo function is working contrary to how you would like.
By the way, let me suggest you to change your binarySearch into this, more readable one:
public static int binarySearch(Student list[], Student key) {
int low = 0;
int high = list.length - 1;
int middle;
int location = -1;
while (low <= high) {
middle = (low + high + 1) / 2;
int compare = list[middle].compareTo(key);
if (compare == 0) {
location = middle;
return location;
} else if (compare > 0) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return location;
}