尝试对对象数组 [比较器] 进行二进制搜索
Attempting a Binary Search on a Object Array [comparator]
为了编写这段代码,我已经苦苦挣扎了几天。基本上,我们必须根据 Student 数组中 Comparable "Student" 对象的 SSN 执行 binarySearch。在 SSN 上执行 binarySearch 后,与该 SSN 的名字和姓氏相关联的学生应该打印出来,并且该学生的 position/location 应该打印出来。我遇到的问题是,当我执行 binarySearch 以查找 Student 的 location/position 时,它总是 returns "-1" 而不是学生的元素位置。有帮助吗?
学生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());
}
}
我在哪里为 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;
}
}
}
}
}
以及我执行二进制搜索的位置
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);
}
当我执行二进制搜索时,它总是 returns -1 而不是学生元素位置
在 binarySearch
while 循环中将此行 list[middle].compareTo(key) < 0
更改为 list[middle].compareTo(key) > 0
。
您的 compareTo
功能似乎与您希望的相反。
顺便说一句,我建议您将 binarySearch 改成这个,更具可读性:
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;
}
为了编写这段代码,我已经苦苦挣扎了几天。基本上,我们必须根据 Student 数组中 Comparable "Student" 对象的 SSN 执行 binarySearch。在 SSN 上执行 binarySearch 后,与该 SSN 的名字和姓氏相关联的学生应该打印出来,并且该学生的 position/location 应该打印出来。我遇到的问题是,当我执行 binarySearch 以查找 Student 的 location/position 时,它总是 returns "-1" 而不是学生的元素位置。有帮助吗?
学生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());
}
}
我在哪里为 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;
}
}
}
}
}
以及我执行二进制搜索的位置
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);
}
当我执行二进制搜索时,它总是 returns -1 而不是学生元素位置
在 binarySearch
while 循环中将此行 list[middle].compareTo(key) < 0
更改为 list[middle].compareTo(key) > 0
。
您的 compareTo
功能似乎与您希望的相反。
顺便说一句,我建议您将 binarySearch 改成这个,更具可读性:
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;
}