ArrayList 二分查找

Question

问题

我想在一个Klant对象上自己实现二分查找方法，该怎么做？ Klant有一些变量。

public class Klant {
public String klantID;
private String voornaam;
private String tussenvoegsel;
private String achternaam;
private int leeftijd;
private static boolean MAN = true;
private String plaats;
private String email;
/*
 *  Getters and setters included 
 */
}

Klant toevoeging = new Klant("FirstName", "middleName", "\Lastname\"", 20, false, "Location", "[e-mail]");
klanten.add(toevoeging);

- user3671459

---

我已经发布了一个答案，我认为它适合您的需求，尽管您的要求并不是非常清楚。请确保在未来撰写更加详细的帖子。阅读Asking section on the help page以获取有关提出易于回答问题的建议。 - Rudi Kershaw

Answer 1

使用Collections.binarySearch(...)

当您在列表上运行Collections.binarySearch(...);时，该列表中的对象必须实现Comparable接口，否则您将需要将一个Comparator传递到binarySearch(...)方法中。

以使用Comparator为例，您可以执行以下操作：

class KlantComparator implements Comparator<Klant> {
    @Override
    public int compare(Klant o1, Klant o2) {
        if(condition)
          return 1;
        else if(condition2)
          return 0;
        else 
          return -1;
    }
}

在上面的代码中，您比较了Klant对象o1和o2，如果o1应排在o2之前，则返回1；如果它们相同，则返回0；如果o1排名低于o2，则返回-1。然后运行二分搜索；

    KlantComparator kc = new KlantComparator();
    ArrayList klants = new ArrayList<Klant>();
    Klant o = new Klant();
    klants.add(o);
    klants.add(new Klant());
    klants.add(new Klant());
    Collections.sort(klants, kc);
    Collections.binarySearch(klants, o, kc);

请注意，上述代码中需要首先对klants集合进行排序，并且二分查找需要使用相同的Comparator来对列表进行排序。

希望这可以帮助您。

进一步阅读：

• Collections API - binarySearch()
• Comparator API
• Comparable API

- Rudi Kershaw

Answer 2

既然您想自己实现，那么Collections.binarySearch就不够用了吗？

好的....

二分搜索:

您有一个已排序的列表。获取中间的元素并与要查找的对象进行比较。如果它小于要查找的元素，则在仅包含更高元素的列表部分中重复搜索。如果它大于要查找的元素，则在仅包含更低元素的列表部分中进行搜索。

那么如何执行二分搜索呢？

您需要一种度量方式，以便为两个对象定义哪个是较低的，哪个是较高的。

您的对象必须实现Comparable 或者 您必须为您的列表定义一个Comparator。

然后您需要实际对列表进行排序。排序将是Collections.sort(myList)。

现在List有size()方法，它将帮助您确定第一个“中间”元素。

伪代码：

 **input** : keyElement

 startIndex = 0;
 endIndex = list.size();

 midIndex = (endIndex+startIndex) / 2;
 while(list.get(midIndex) !=  keyElement) {
     if (list.get(midIndex) < keyElement) {
         startIndex = midIndex;
     } else {
         endIndex = midIndex;
     }
     midIndex = (endIndex+startIndex) / 2;
 }

 return midIndex;

大致上是这样（在边界处要小心...也许需要+/-1）。

- Terry Storm