java - 在二进制搜索中，如果找不到该元素，为什么约定从它应该做的地方减去一个？

Question

我知道这已经深入到本质上了，但是当进行二进制搜索并且未找到元素时，返回 (-(insertion point) -1) 的合理性是什么。特别是 -1 部分。 Java 就是这样做的，我不明白他们为什么制定约定 -1 而不是 -(插入点)。显然，否定是表示该值实际上并未在数组/列表中找到。我猜它来自 C，在 C 中更容易进行一些取反和减一的按位运算。

注意:我看到用 C、C++ 和 Java 编写的代码使用了这个约定，我想知道这个约定是从哪里来的？

Answer 1

这是因为插入点可能为零，而 int 没有 -0(与 float 不同)，因此您需要一些其他方式来明确指示它。

正如它在 Javadoc 中所说的那样:

Note that this guarantees that the return value will be >= 0 if and only if the key is found.

当然还有其他方式表示插入位置；这恰好非常优雅，因为它不需要额外的信息，例如容器的大小，以便用于适本地插入元素。

---

就 session 的起源地而言 - 我敢打赌是时间的迷雾!

作为纯粹的猜想，我可以想象它会出现在 C(或者甚至更早的语言)中，它是一种比其他方法更简洁的编码值的方法。

“明显”的替代编码可能是使用符号位来指示存在/不存在，其余位指示插入位置:

S PPPP....P
^            0 means "present", 1 means "absent"
  ^---....^  These bits denote the position in the container.

要在设置了符号位的情况下提取位置，需要屏蔽这些位。这在 Java 中很容易，其中 int 被定义为具有 32 位(只需使用 value & 0x7FFFFFF)；但是要用可移植的 C 语言编写它，您需要执行以下操作:

value = binarySearch(...);
if (value < 0) {
  insertionPosition = value & ~(1 << sizeof(int) * 8 - 1);
  ...
}

(请原谅我，如果这不是很正确 - 这就是为什么 Java 程序员不应该尝试编写 C...)

即使宽度固定，也有点神秘:

value = binarySearch(...);
if (value < 0) {
  insertionPosition = value & 0x7FFFFFFF;  // What's this magic number?!
  ...
}

如果你不得不在很多地方写它，那是相当丑陋的，而且很容易出错。当然，您可以编写一个小方法来为您完成此数学运算，但方法调用的成本很高(至少，它们在过去可能已经存在)。

使用 (-(insertion point) -1) 约定，您可以编写简单、易于阅读、快速的代码:

value = binarySearch(...);
if (value < 0) {
  insertionPosition = -value - 1;
  ...
}