Как реализовать двоичный поиск вручную в моем ADT [JAVA]

Question

Хорошо, я застрял на том, как мне реализовать этот двоичный поиск, который будет получать данные из других классов.

Я пытаюсь реализовать его в моем собственном ADT.

Я реализовалПеречислите ADT вручную, но теперь я хочу добавить операцию поиска, которая использует двоичный алгоритм поиска вручную и не использует встроенный Java API.

Пример. Это мой интерфейс отсортированного списка, который я реализовал вручную.

public class SortedArrayList<T extends Comparable<T>> implements SortedListInterface<T>{



   private boolean binarySearch(// What parameters should I receive from Student Object?) {
       // This will be my binary search implementation
   }         



}

Проблема в том, что я буду создавать класс Student, в который я добавлю экземпляры класса Student в приведенный выше список sortedArrayList.

Например, как я собираюсь получить данные для включения в алгоритм двоичного поиска в обобщенном типе sortedArrayList?

Обратите внимание, что я не допускаетсячтобы использовать любой встроенный API-интерфейс JAVA, все должно быть реализовано вручную, иначе я могу закончить это легко, но сейчас это сложно, так как он ограничен.

Пример Я хочу выполнить бинарный поиск по имени ученика из класса ученика,Как мне нужно будет внедрить и получить данные в эту мою ADT, реализованную вручную?

public class SortedArrayList<T extends Comparable<T>> implements SortedListInterface<T>{

     private T[] list;


   private boolean binarySearch(int first, int last, T desiredItem) {

       int mid = (first + last) / 2;

          if(desiredItem.getFullName().equals(list[mid]) 
                // This part over here. How do I access attributes from Student class in this ADT so that I can access the data and do comparison for the binary search..

   }         



}

Как получить доступ к атрибутам из класса Student в моей собственной ADT, чтобы я мог выполнять сравнения при бинарном поискеалгоритм?!

Я буквально застрял.

Буду признателен, если кто-нибудь даст мне указания. Я повторяю еще раз: нет встроенных API из JAVA, реализация только вручную

ADT SortedList Interface

    public interface SortedListInterface <T extends Comparable<T>> {


        public boolean add(T element);


        public T get(int index);


        public boolean search(T element);


        public T remove(int index);


        public void clear();


        public int getLength();


        public boolean isEmpty();


        public boolean isFull();


    }

ADT SortedList РеализацияКод

public class SortedArrayList<T extends Comparable<T>> implements SortedListInterface<T>{

  //Data Types  

  private T[] list;
  private int length;
  private static final int SIZE = 10;


  // Constructors

  public SortedArrayList() {
    this(SIZE);
  }

  public SortedArrayList(int size) {
    length = 0;
    list = (T[]) new Comparable[SIZE]; // an array of instances of a class implementing Comparable interface and able to use compareto method but its overidden instead
  }


  // Setter & Getters

  @Override
  public int getLength() {
    return length;
  }

  @Override
  public boolean isEmpty() {
    return length == 0;
  }

  @Override
  public boolean isFull() {
    return false;
  }

  @Override
  public void clear() {
    length = 0;
  }


  // Array Expansion

  private boolean isArrayFull() {
    return length == list.length;
  }

  private void expandArray() {
    T[] oldList = list;
    int oldSize = oldList.length;

    list = (T[]) new Object[2 * oldSize];

    for (int i = 0; i < oldSize; i++) // copy old array elements into new array elements
      list[i] = oldList[i];

  }




  // ADT METHODs


  // Add New Elements Function


  @Override
  public boolean add(T element) {
    int i = 0;

    while (i < length && element.compareTo(list[i]) > 0) // return 0 with equal , return more than 1 if element larger than list[i] , return -1 if less
      i++;

    makeRoom(i + 1);
    list[i] = element;
    length++;
    return true;
  }  


  private void makeRoom(int index) {  // accepts given index
    int newIndex = index - 1;
    int lastIndex = length - 1;

    for (int i = lastIndex; i >= newIndex; i--) 
      list[i + 1] = list[i];

  }



  //Remove Elements Function

  @Override
  public T remove(int index) {  // accepts given index

    T result = null;

    if ( index >= 1 && index <= length ) {

      result = list[index - 1];

      if (index < length) 
        removeGap(index);

      length--;
    }

    return result;
  }

  private void removeGap(int index) { // accepts given index and remove the gap where the element its removed

    int removedIndex = index - 1;
    int lastIndex = length - 1;

    for (int i = removedIndex; i < lastIndex; i++) 
      list[i] = list[i + 1]; // shifts elements back to remove the gap

  }


  // Get Element

  @Override
  public T get(int index) { // accepts given index and return the object

    T object = null;

    if ( index >= 1 && index <= length) 
      object = list[index - 1];

    return object;

  }


  // Search Algorithms

  @Override
  public boolean search(T element) {

    return binarySearch(element);

  }

  private boolean binarySearch(// Implementation here) {
       // Implementation here
  } 




  //To String Method

  @Override
  public String toString() {

    String result = "";

    for (int i = 0; i < length; i++) 
      result += list[i] + "\n";

    return result;

  }



}

Внедрение ученического класса

public class Student implements Comparable<Student>{


   // Data Types 

   private Name name;
   private char gender;
   private String icNo;
   private String mobileNo;
   private Course course;
   private int group;
   private String dOB;


   // Constructors

   public Student() {
   }

   public Student(Name name, char gender, String icNo, String mobileNo, Course course, int group, String dOB) {
        this.name = name;
        this.gender = gender;
        this.icNo = icNo;
        this.mobileNo = mobileNo;
        this.course = course;
        this.group = group;
        this.dOB = dOB;
    }

   public Student(Name name) {
        this.name = name;
    }


   // setter

   public void setName(Name name) {
        this.name = name;
    }

    public void setGender(char gender) {
        this.gender = gender;
    }

    public void setIcNo(String icNo) {
        this.icNo = icNo;
    }

    public void setMobileNo(String mobileNo) {
        this.mobileNo = mobileNo;
    }

    public void setCourse(Course course) {
        this.course = course;
    }

    public void setGroup(int group) {
        this.group = group;
    }

    public void setdOB(String dOB) {
        this.dOB = dOB;
    }


    // getter


    public Name getName() {
        return name;
    }

    public char getGender() {
        return gender;
    }

    public String getIcNo() {
        return icNo;
    }

    public String getMobileNo() {
        return mobileNo;
    }

    public Course getCourse() {
        return course;
    }

    public int getGroup() {
        return group;
    }

    public String getdOB() {
        return dOB;
    }

    @Override
    public String toString() {
        return "Student{" + "name=" + name + ", gender=" + gender + ", icNo=" + icNo + ", mobileNo=" + mobileNo + ", course=" + course + ", group=" + group + ", dOB=" + dOB + '}';
    }

   public int compareTo(Student object) { // Sort according to name if name same then sort according to gender and so on.

    int c = this.name.getFullName().compareTo(object.getName().getFullName());

    if(c == 0)
        c = this.gender - object.getGender(); 

    if(c == 0)
        c = this.icNo.compareTo(object.getIcNo());  

    if(c == 0)
        c = this.mobileNo.compareTo(object.getMobileNo());

    if(c == 0)
        c = this.group - object.getGroup();

    if(c == 0)
        c = this.dOB.compareTo(object.getdOB());

    return c;

  }


}

Курс класса

public class Course {


    // Data Types

    private String courseCode;
    private String courseName;
    private double courseFee;


    // Constructors

    public Course() {
    }

    public Course(String courseCode, String courseName, double courseFee) {
        this.courseCode = courseCode;
        this.courseName = courseName;
        this.courseFee = courseFee;
    }

    // setter

    public void setCourseCode(String courseCode) {
        this.courseCode = courseCode;
    }

    public void setCourseName(String courseName) {
        this.courseName = courseName;
    }

    public void setCourseFee(double courseFee) {
        this.courseFee = courseFee;
    }


    // getter

    public String getCourseCode() {
        return courseCode;
    }

    public String getCourseName() {
        return courseName;
    }

    public double getCourseFee() {
        return courseFee;
    }

    @Override
public String toString() {
    return "CourseCode = " + courseCode + "Course Name = " + courseName + "Course Fee = " + courseFee;
}




}

Название класса

public class Name {

    // Data Types

    private String firstName;
    private String lastName;


    // Constructors

    public Name() {
    }

    public Name(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }

    // setter

    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }

    public void setLastName(String lastName) {
        this.lastName = lastName;
    }

    // getter

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public String getFullName(){
        return firstName + " " + lastName;
    }

    @Override
    public String toString() {
        return "Name{" + "firstName=" + firstName + ", lastName=" + lastName + '}';
    }

Answer 1

Алгоритм двоичного поиска основан на сравнении искомого значения со значениями в искомом списке. Вот почему объявление вашего класса, которое реализует SortedListInterface:

SortedArrayList<T extends Comparable<T>>

Обратите внимание: extends Comparable<T>.
Comparable - это интерфейс, через который вы можете сравнивать два объекта. Следовательно, в методе search(), который вы должны реализовать, вы знаете, что каждый объект в списке определяет метод compareTo(), и вы просто используете этот метод для сравнения искомого объекта с отдельными объектами в списке.

Вот простая реализация алгоритма двоичного поиска в контексте вашего проекта.

private T[] list; // The list to search.

private int count; // The number of non-null elements in 'list'.

public boolean search(T element) {
    boolean found = false;
    int lo = 0;
    int hi = count - 1;
    while (lo <= hi) {
        int mid = lo + hi / 2;
        if (list[mid].compareTo(element) < 0) {
            lo = mid + 1;
        }
        else if (list[mid].compareTo(element) > 0) {
            hi = mid - 1;
        }
        else if (list[mid].equals(element)) {
            found = true;
            break;
        }
    }
    return found;
}

С помощью метода у вас есть параметр метода. В коде метода вы используете имя параметра. Но когда вы вызываете этот метод из другого кода, вы предоставляете значение, которое заменяет параметр. Таким же образом в приведенном выше коде используется параметр type , который заменяется именем фактического класса при создании экземпляра класса SortedArrayList. В вашем случае T заменяется на Student, а класс Student должен реализовать метод compareTo(). Следовательно, метод search() в классе SortedArrayList не должен знать о членах в классе Student.

Так что вы сначала должны создать экземпляр SortedArrayList, например:

SortedArrayList<Student> theList = new SortedArrayList<>();

Затем вы можете вызвать метод search() следующим образом:

Student s = new Student(/* relevant parameter values */);
theList.search(s);

РЕДАКТИРОВАТЬ

Я понимаю, что вы не обязательно хотите искать Student, выможет захотеть найти Name студента или номер мобильного телефона студента. В этом случае я считаю, что вам нужен Comparator . Вот код для класса SortedArrayList с добавлением Comparator

import java.util.Comparator;
import java.util.Objects;

public class SortedArrayList<T extends Comparable<T>> implements SortedListInterface<T> {
    private static final int SIZE = 10;

    private Comparator<? super T> comparator;
    private T[] list;
    private int count;

    @SuppressWarnings("unchecked")
    public SortedArrayList(Comparator<? super T> c) {
        comparator = c;
        list = (T[]) new Comparable[SIZE]; // No way to verify that 'list' only contains instances of 'T'.

        /* NOTE: Following is not allowed.
        list = new T[SIZE]; // Cannot create a generic array of T
        */
    }

    @Override
    public boolean add(T element) {
        Objects.requireNonNull(element, "Cannot add null element.");
        boolean result = false;
        if (count == 0) {
            list[0] = element;
            count = 1;
            result = true;
        }
        else {
            if (!isFull()) {
                int i = 0;
                while (list[i] != null) {
                    if (element.compareTo(list[i]) < 0) {
                        break;
                    }
                    i++;
                }
                if (list[i] != null) {
                    for (int j = count - 1; j >= i; j--) {
                        list[j + 1] = list[j];
                    }
                }
                list[i] = element;
                count++;
                result = true;
            }
        }
        return result;
    }

    @Override
    public T get(int index) {
        checkIndex(index);
        return list[index];
    }

    @Override
    public boolean search(T element) {
        if (comparator == null) {
            return binarySearchComparable(element);
        }
        else {
            return binarySearchComparator(element);
        }
    }

    @Override
    public T remove(int index) {
        checkIndex(index);
        T removed = list[index];
        list[index] = null;
        for (int i = index; i < count; i++) {
            list[i] = list[i + 1];
        }
        count--;
        list[count] = null;
        return removed;
    }

    @Override
    public void clear() {
        for (int i = 0; i < count; i++) {
            list[i] = null;
        }
        count = 0;
    }

    @Override
    public int getLength() {
        return count;
    }

    @Override
    public boolean isEmpty() {
        return count == 0;
    }

    @Override
    public boolean isFull() {
        return count == SIZE;
    }

    private boolean binarySearchComparable(T element) {
        boolean found = false;
        int lo = 0;
        int hi = count - 1;
        while (lo <= hi) {
            int mid = lo + hi / 2;
            if (list[mid].compareTo(element) < 0) {
                lo = mid + 1;
            }
            else if (list[mid].compareTo(element) > 0) {
                hi = mid - 1;
            }
            else if (list[mid].equals(element)) {
                found = true;
                break;
            }
        }
        return found;
    }

    private boolean binarySearchComparator(T key) {
        int low = 0;
        int high = count - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            T midVal = list[mid];
            int cmp = comparator.compare(midVal, key);
            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return true; // key found
        }
        return false;  // key not found.
    }

    private void checkIndex(int index) {
        if (index < 0) {
            throw new IllegalArgumentException("Negative index.");
        }
        if (index >= count) {
            throw new IllegalArgumentException(String.format("Supplied index %d is not less than %d", index, count));
        }
    }
}

Вот пример Comparator для Name Student

import java.util.Comparator;

public class NameComparator implements Comparator<Student> {

    @Override
    public int compare(Student student1, Student student2) {
        int result;
        if (student1 == null) {
            if (student2 == null) {
                result = 0;
            }
            else {
                result = -1;
            }
        }
        else {
            if (student2 == null) {
                result = 1;
            }
            else {
                result = student1.getName().getFullName().compareTo(student2.getName().getFullName());
            }
        }
        return result;
    }
}

Таким образом, для поиска в списке по любой комбинации атрибутов Student просто реализуйте соответствующий Comparator и передайте его классу SortedArrayList.