java - 如何在自己的ADT中手动实现二分查找[JAVA]

标签 java algorithm binary-search abstract-data-type

好吧，我不知道如何实现从其他类接收数据的二分搜索。

我正在尝试在我自己的 ADT 中实现它。

我已经手动实现了一个列表 ADT，但现在我想添加一个搜索操作，该操作手动使用二分搜索算法，并且不使用任何内置的 Java API。

示例这是我手动实现的排序列表接口(interface)。

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 类，将学生类的实例添加到上面的排序数组列表中。

就像我将如何接收要放入泛型类型的 SortArrayList 中的二分搜索算法的数据？

请注意，我不允许使用任何 JAVA 内置 API，一切都必须手动实现，否则我可以轻松完成此操作，但由于其限制，现在很痛苦。

示例我想按学生类(class)中的学生姓名进行二分搜索。我需要如何实现数据并将其接收到我的手动实现的 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 中，以便我可以对二分搜索算法进行比较？!

我真的被困住了。

如果有人给我指路，我将不胜感激。 我再次重复一遍，没有来自 JAVA 的内置 API，仅手动实现

ADT排序列表接口(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;

  }



}

学生类(class)实现

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;

  }


}

类(class)类别

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 + '}';
    }

最佳答案

二分搜索算法依赖于将正在搜索的值与正在搜索的列表中的值进行比较。这就是为什么你的类声明实现 SortedListInterface是:

SortedArrayList<T extends Comparable<T>>

注意 extends Comparable<T> .
Comparable是一个接口(interface)，通过它您可以比较两个对象。因此在 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 {
            found = true;
            break;
        }
    }
    return found;
}

有了方法，就有了方法参数。在方法代码中，您使用参数名称。但是，当您从其他代码调用该方法时，您需要提供一个值来替换该参数。同样，上面的代码使用 type 参数，当您创建类 SortedArrayList 的实例时，该参数将替换为实际类的名称。 。在你的情况下，T替换为Student和类(class)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 {
                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类。

编辑2

根据您 2019 年 11 月 17 日的评论。
以下是“姓名和手机”的代码 Comparator 。正如我在之前的编辑中所写，您需要编写适当的 Comparator对于 Student 的给定组合属性。

import java.util.Comparator;

/**
 * Compares {@code Student} name and mobile phone number.
 */
public class NameAndMobileComparator 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());
                if (result == 0) {
                    result = student1.getMobileNo().compareTo(student2.getMobileNo());
                }
            }
        }
        return result;
    }
}

关于java - 如何在自己的ADT中手动实现二分查找[JAVA]，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58780787/

上一篇：java - 如何将多行StringBuilder转换为字符数组？

下一篇：java - 如何删除 Dropbox 文件？

相关文章：

java - validate() 树在 L&F 更改时抛出 NullPointerException？

algorithm - 比较顺序搜索和二分搜索

algorithm - 如何在 O(n) 时间内对单链表进行二分查找？

java - 如何找出 eclipse 项目中使用了哪些版本的 JAR

java - 文本简化工具 (Java)

java - Derby客户端jdbc驱动连接错误: Failed to create database 'sample'

java - 数组中 N 个元素的绝对差的最大和

JavaScript 算法插入排序略有偏差

algorithm - 我如何开始使用 Gomoku？

algorithm - 最大子数组和模 M

©2024 IT工具网  联系我们