1

如果我想调用 binarySearch() 方法来执行搜索操作，是否需要实现比较器或可比较？我在尝试调用 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 方法中作为参数传递什么。

请帮我

4

5 回答 5

4

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

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

 Collections.binarySearch(list, studentToBeFound, comparator);

studentToBeFound作为一个Student实例，比较器与Comparator<Student>您在Collection.sort().

只需重用您以前的 Comparator 比较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());
于 2013-02-15T14:45:54.127 回答
1

二进制搜索需要一个排序列表。

这种搜索基于分区：

  1. 取中间元素并将其与参考进行比较。
  2. 如果比较表明您的引用“较低”，则二进制搜索在集合的前半部分继续，或者如果它“较高”，则在后半部分继续。
  3. 当比较返回0时，元素被找到。

考虑到这一点，实际上需要对列表进行排序。您可以通过不同的方式进行操作：

  • 借助 a 对其进行排序，Comparator然后调用binarySerarch
  • 对实现接口的元素集合进行排序Comparable，然后调用binarySearch
  • binarySearch如果您提供所需的，则将排序留给方法Comparator。
于 2013-02-15T14:51:37.677 回答
1

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

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

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

public class StudentComparator implements Comparator<Student>

于 2013-02-15T14:49:39.667 回答
1

binarySearch 方法的第三个参数必须是 Comparator，因为你的 Student 类没有实现 Comparator 接口，所以抛出异常。

binarySearch(List list, Object key, Comparator c)

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

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

于 2013-02-15T14:43:56.253 回答
1

简短的回答是肯定的 - 二进制搜索不知道Student您正在搜索的是“更大”还是“更小”然后是列表中的每个，因此无法搜索。
您想Student使用比较器中已有的代码实现可比较：

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);
于 2013-02-15T14:45:34.920 回答