Collections.binarySearch(list,key)*-2 在 java 列表中找不到键时，键是 lower_bound 吗？

Question

考虑以下代码。

  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 class 提供的 binarySearch 方法。当键不在列表中时，它会以负数给出这些奇怪的数字。我将它们映射到它们的下限和上限。我研究了几个例子并且总是做对。

see this

对于我给它的每个输入 return 正确的列表内的上限和下限。谁能给我解释一下？引擎盖里面发生了什么？

Answer 1

这是 Collections.binarySearch 的正确记录行为。来自 JavaDoc：

the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

注意最后一句话（我自己强调），如果找到密钥，保证 return 值为 0 或正数。这意味着如果输入 List.

中不存在所需元素，则 returned 为负值

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

Collections.indexedBinarySearch 从行 278
Collections.iteratorBinarySearch 从行 298

...他们两个 return 以下以防找不到密钥：

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

因此 returned 值是搜索元素 预期位于 位置的负索引。

Collections.binarySearch(list,key)*-2 在 java 列表中找不到键时，键是 lower_bound 吗？

Is Collections.binarySearch(list,key)*-2 is lower_bound for key when key not found in java List?

java

collections

binary-search

lower-bound

upperbound