当元素不存在并且不是-insertion_point时，为什么Collections.binarySearch返回-(insertion_point - 1)？

Question

我一直在使用binarySearch方法，并想知道为什么当元素不存在且不是-insertion_point时，Collections.binarySearch会返回-(insertion_point - 1)？我理解为什么它是负的，但是为什么是-1？

Answer 1

因为你不能有负0。

考虑一下如果没有-1的情况。如果在索引0处找到一个元素，它将返回0。如果没有找到一个元素，但是它的插入点是0，那么它也会返回0。你如何区分这两种情况？添加了-1之后，它们现在分别返回0和-1，让您可以区分它们。

它是-(insertion point) - 1，它与你的问题略有不同。

Answer 2

The documentation说：

返回

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

重要的是最后一句话：

请注意，当且仅当找到密钥时，这将保证返回值为>= 0。

If effect，您将从binarySearch返回两个值，这两个值以一种聪明的方式组合在一起。您可以获得有关该项是否存在(通过结果的符号)以及它所属的位置(结果的大小)的信息。