1

考虑以下代码。

  List<Integer> list = new Random().ints(10,1,50).boxed().collect(Collectors.toList());
        list.sort(Comparator.naturalOrder());
        System.out.println(list);
        System.out.print("Enter key :");
        Scanner sc = new Scanner(System.in);
        int key = sc.nextInt();
        int ans = Collections.binarySearch(list, key);

        String result = String.format("ans = %d, list.at(ans*-1) = %d , lower bond = %d , upper bound = %d ", ans,list.get(ans*-1),list.get(ans*-1 -2 ) , 
                list.get(ans * -1 -1));
        System.out.println(result);

我正在研究 Collections 类给出的 binarySearch 方法。当 key 不在列表中时，它会将这些奇怪的数字设为负数。我将它们映射到它们的下限和上限。我研究了几个例子并且总是做对了。

看到这个

截屏

对于我给它的每个输入，它都会在列表中返回正确的上限和下限。谁能给我解释一下？引擎盖内发生了什么？

4

1 回答 1

3

这是Collections.binarySearch. 来自 JavaDoc：

搜索关键字的索引，如果它包含在列表中；否则，（-（插入点）- 1）。插入点定义为将键插入列表的点：第一个元素的索引大于键，如果列表中的所有元素都小于指定的键，则为 list.size()。请注意，这保证了当且仅当找到键时，返回值将 >= 0。

注意最后一句话（我自己强调的），如果找到密钥，则保证返回值为 0 或正数。这意味着如果输入中不存在所需的元素，则返回负值List。

编辑：负值实际上并不像看起来那样不可预测。浏览源代码java.util.Collections及其计算结果的私有方法...

  • Collections.indexedBinarySearch从线278
  • Collections.iteratorBinarySearch从线298

...如果找不到密钥，它们都会返回以下内容：

return -(low + 1);  // key not found

因此，返回值是搜索元素预期位于的负索引。

于 2020-05-22T11:53:16.007 回答