0 
public class BinarySearchCollections {
  public static void search(List<String> list) {
    list.clear();
    list.add("b");
    list.add("a");
    list.add("c");
    System.out.println(Collections.binarySearch(list, "b"));
    System.out.println(list);
  }
  public static void main(String[] args) {
    List<String> lis = new ArrayList<String>();
    BinarySearchCollections bs = new BinarySearchCollections();
    bs.search(lis);
  }
}

Here I am getting ans as -3 (as it is telling me at what location it is going to be added) but I already have b in my list.

4

2 回答 2

1

您的原始列表未排序，因此二进制搜索会给您一个无意义的答案。

想象一下它实际采取的步骤：

“是 b > a 吗？是的，所以往高处看。”

“是 b > c 吗？不，但我们不能再低了，所以在索引 2 处插入（也就是返回 -3。）”

如果你想让二分搜索起作用，给它一个可以采取有意义步骤的列表，然后给你正确的答案。

于 2013-05-02T18:17:57.253 回答
1

Collections.binarySearch()不确保在尝试搜索之前对列表进行排序。在调用之前，您需要确保是这种情况binarySearch()。

如果它确实首先检查列表，它会将 O(lg(n)) 搜索变成 O(n+lg(n)) 检查/搜索，从而降低性能。（O(nlg(n)) 如果它也必须对列表进行排序）。

您可能应该检查List.Sort()方法。

于 2013-05-02T18:20:19.590 回答