为什么 binarysearch 方法将负返回值减少 1

Question

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

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

如果在数组中找不到匹配项，我无法理解为什么 return (-(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 是一个合法的插入点，但你不能只是 return 0，因为那意味着在索引 0 处找到了密钥。

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

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

使用任何大于 1 的减数将导致接近 Integer.MAX_VALUE 的最高索引出现整数下溢。有关 ~ 运算符的更多信息，请参阅 Explanation of Bitwise NOT Operator.

Answer 2

不，插入点不一定等于数组的大小；有问题的项目理论上可以插入数组中的任何位置。

可能找不到该项目，但也可能少于（已排序）数组中的所有项目。这意味着插入点是 0。但是使用 -(insertion point) 意味着 0 将被 returned。这意味着该项目 在位置 0 找到 。他们减去一个来避免这种冲突，这样一个项目比所有其他项目少 return -1.

当然，如果你真的想在数组中插入一个项目，你必须加一个然后取反才能找到插入位置。但是考虑到您必须移动数组的内容以为数组中的新项腾出空间，做一些额外的数学运算是微不足道的。

二分查找过程完成查找插入点的工作。如果它只是 returned -1 你必须重新搜索才能找到插入点。该方法在 returning 一个 "not found" 场景时为您提供了一些额外信息，如果需要将项目插入到数组中，可以使用这些信息。它只需要避免 0 可能表示 "found at first position" 和 "not found, but insert at the beginning".

的情况

为什么 binarysearch 方法将负返回值减少 1

Why binarysearch method reduces the negative returned value by 1

java

arrays

binary-search