为什么二进制搜索方法将负返回值减少 1

Question

说说Arrays中定义的这个方法：

public static int binarySearch(int[] a, int key)

我无法理解为什么返回(-(insertion point) - 1)而不是-(insertion point)在数组中找不到匹配项的情况。

https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[],%20int)

这可能是Math.abs((-(insertion point) - 1))等于数组大小的原因吗？

如果你想知道我为什么要问这个问题，我看到为了找到插入点，我基本上必须做减法。

int returnedVal = Arrays.binarySearch(arr, needle);
if (returnedVal < 0) 
     insertionPoint = Math.abs(returnedVal) - 1; 

Answer 1

因为 0 是一个合法的插入点，但您不能只返回 0，因为这意味着在索引 0 处找到了键。

编辑：请注意，选择减去 1 而不是另一个数字并不是任意的。 -a - 1等于~a（a 的按位求反），该函数对所有正（和负）整数都是双射的，因为它只是翻转位并使用整个整数范围：~Integer.MIN_VALUE == Integer.MAX_VALUE, ~(-1) == 0。还要注意的是~(~a) == a。

您可以通过执行 找到插入点~returnedVal。Java 中的整数总是使用二进制补码，所以等价是有效的。

对于 Integer.MAX_VALUE 附近的最高索引，使用任何大于 1 的减数都会导致整数下溢。有关 ~ 运算符的更多信息，请参阅按位非运算符的说明。