二进制搜索对列表

Question

我需要找到匹配 element 的 elem。
我的程序可以运行，但效率不高。我有一个非常大的 ArrayList<Obj> pairs（超过 4000 个元素），我使用二进制搜索来查找匹配的索引。

public int search(String element) {
  ArrayList<String> list = new ArrayList<String>();
  for (int i = 0; i < pairs.size(); i++) {
      list.add(pairs.get(i).getElem());
  }
  return index = Collections.binarySearch(list, element);
}

我想知道是否有比使用循环将一半 ArrayList 对复制到新的 ArrayList 列表更有效的方法。 Obj 的构造函数：Obj x = new Obj(String elem, String word);

Answer 1

如果您的主列表 (pairs) 没有改变，那么我建议创建一个 TreeMap 以保持反向 index 结构，例如：

List<String> pairs = new ArrayList<String>(); //list containing 4000 entries

Map<String, Integer> indexMap = new TreeMap<>();

int index = 0;
for(String element : pairs){
    indexMap.put(element, index++);
}

现在，在搜索元素时，您需要做的就是：

indexMap.get(element);

这将为您提供所需的 index 或 null（如果元素不存在）。此外，如果一个元素可以多次出现在列表中，则可以将 indexMap 更改为 Map<String, List<Integer>>.

您当前的算法迭代列表并调用二进制搜索，因此迭代的复杂度为 O(n) 和 O(log n) 而 TreeMap 保证 log(n) 时间成本，因此它会快很多。

Here 是 TreeMap 的文档。

Answer 2

看来问题已经解决了。由于我的问题是 ArrayList 对类型是 Obj 和 element 类型是字符串，我不能使用 Collections.binarySearch，我决定创建一个新变量 Obj x = new Obj(element, "");。看起来字符串不会引起任何问题（它通过了我的 JUnit 测试），因为我的 compareTo 方法比较两个 elem 并忽略 Obj x.[=17= 的第二个变量]

我更新的方法：

public int search(String element) {
  Obj x = new Obj(element, "");
  int index = Collections.binarySearch(pairs, x);

二进制搜索对列表

Binary search over a list of pairs

java

arraylist

binary-search