java我可以调用binarySearch方法而不实现comparator/comparable吗？

Question

如果要调用binarySearch（）方法执行搜索操作，是否需要实现comparator或comparable？我 我在尝试调用binarySearch（）方法时遇到异常

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

class Student implements{
private int id;
private String name;

public Student(int id, String name){
    this.id = id;
    this.name = name;
}

public Student() {
    // TODO Auto-generated constructor stub
}

public int getId(){
    return id;
}
public String getName(){
    return name;
}

}
public class CollectionSearchDemo {


public static void main(String[] args) {

    List<Student> list = new ArrayList<Student>();
    list.add(new Student(3, "ouier"));
    list.add(new Student(2, "fdgds"));
    list.add(new Student(7, "kiluf"));
    list.add(new Student(1, "6trfd"));
    list.add(new Student(8, "hjgas"));
    list.add(new Student(5, "ewwew"));

    Collections.sort(list, new Comparator<Student>() {

        @Override
        public int compare(Student arg0, Student arg1) {

            return arg0.getId() - arg1.getId();
        }
    });

    Iterator iterator = list.iterator();
    while(iterator.hasNext()){
        Student student = (Student) iterator.next();
        System.out.print(student.getId()+":"+student.getName()+" ");
    }

    System.out.println("I want to do searching ");
    System.out.println("\n2 is at:"+Collections.binarySearch(list, 2, new Student()));
            // facing exception when i invoke binarySearch method.
}
}

尝试搜索“new Student（）”或“CollectionSearchDemo”作为参数时发生异常。 我不知道在binraySearch方法中应该传递什么作为参数

请帮帮我

Answer 1

如果我们不知道如何排序，列表就无法排序。二进制搜索算法要求对列表进行排序，它使用列表的顺序来搜索列表，并在每次迭代中将搜索字段对半。但是，要知道学生x是在列表的前半部分还是后半部分，我们需要知道这个列表是如何排序的

选项1:public class Student implements Comparable<Student>

选项2：为学生编写一个比较类

public class StudentComparator implements Comparator<Student>

Answer 2

二进制搜索需要排序列表

这种搜索基于分区：

1. 取中间元素并将其与参考进行比较
2. 如果比较结果表明你的参考值是“较低”的，二进制搜索将在集合的前半部分继续进行；如果参考值是“较高”，二进制搜索将在后半部分继续进行
3. 当comparation返回0时，找到了元素

考虑到这一点，实际上需要对列表进行排序。你可以用不同的方式来做：

• 借助Comparator对其进行排序，然后调用binarySerarch
• 对实现Comparable接口的元素集合进行排序，然后调用binarySearch
• 如果提供了所需的^{，则将排序留给binarySearch方法

Answer 3

有两种方法可以使用Collections.binarySearch。第一个元素只有一个元素列表和一个键，但这些元素必须实现Comparable。第二种方法是使用键和比较器。如果你不想Student实现Comparable，你必须使用这个

所以你必须写下这样的东西：

 Collections.binarySearch(list, studentToBeFound, comparator);

其中studentToBeFound是Student实例，比较器是Comparator<Student>实例，就像您在Collection.sort()中使用的那样

只需重复使用之前与Id进行比较的比较器：

private static final class StudentComparator implements Comparator<Student> {
  @Override
  public int compare(Student arg0, Student arg1) {

    return arg0.getId() - arg1.getId();
  }
}

然后，如果你想找到Id等于2的学生：

Student studentToBeFound = new Student(2, "dummy string");

并与binarySearch一起使用：

int indexInList = Collections.binarySearch(list, studentToBeFound, new StudentComparator());

Answer 4

binarySearch方法的第三个参数必须是Comparator，因为您的学生没有实现Comparator接口，所以引发了异常

binarySearch(List list, Object key, Comparator c)

阅读这里：http://docs.oracle.com/javase/6/docs/api/java/util/Collections.html

参数c必须是实现Comparator的类的实例

Answer 5

简而言之，答案是肯定的——二进制搜索不知道您正在搜索的Student比列表中的每个都“大”还是“小”，因此无法搜索
您希望使用comparator中已有的代码在Student上实现comparable：

public class Student implements Comparable<Student> {
//stuff
 @Override
 public int compareTo(Student o) {
  return getId() - o.getId();
 }
}

然后你的代码看起来像这样：

final Set<Student> set = new TreeSet<Student>();
//add students etc...
final Student found = Collections.binarySearch(set, studentToLookFor);