Попытка двоичного поиска в массиве объектов [компаратор] - PullRequest
Новая
       90

Попытка двоичного поиска в массиве объектов [компаратор]

0 голосов
/ 25 апреля 2020

Я пару дней пытался написать этот код. По сути, мы должны выполнить бинарный поиск на основе SSN сопоставимых объектов "Student" в массиве Student. После выполнения бинарного поиска по SSN студент, связанный с именем и фамилией этого SSN, должен распечатать, а также указать местоположение / местоположение этого студента. Проблема, с которой я столкнулся, заключается в том, что когда я выполняю двоичный поиск, чтобы найти местоположение / позицию студента, он всегда возвращает «-1», а не позицию элемента студента. Любая помощь?

Студенческий класс 

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;

                }       
            }

        }

    }

}

и где я выполняю мой 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);

    }

Когда я выполняю этот двоичный поиск, он всегда возвращает -1, а не позицию элемента студента

1 Ответ

0 голосов
/ 25 апреля 2020

Измените эту строку list[middle].compareTo(key) < 0 на list[middle].compareTo(key) > 0 внутри binarySearch while-l oop.

Кажется, что ваша функция 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;
}
...