在binarysearch中,如果找不到该元素,为什么约定从它应该从哪里减去？

Question

我知道这可以归结为细节,但是当进行二元搜索并且找不到元素时,返回的理性是什么(-(insertion point) -1).特别是-1部分.这就是Java如何做到这一点,我不明白为什么他们制定了惯例-1而不仅仅是-(insertion point).显然,否定的是表明在数组/列表中实际找不到该值.我猜它来自C,它更容易做一些否定和减去一个的按位操作.

注意:我见过使用这种约定用C,C++和Java编写的代码,我想知道约定来自哪里？

Answer 1

这是因为插入点可能为零,并且您没有-0用于int(与浮点数不同),因此您需要一些其他方式来明确指示它.

正如它在Javadoc中所说:

请注意,当且仅当找到密钥时,这可以保证返回值> = 0.

当然,还有其他方式来表示插入位置; 这恰好是相当优雅的,因为它不需要额外的信息,例如容器的大小,以便用于适当地插入元素.

就会议出现的地方而言 - 时间的迷雾,我敢打赌!

作为纯粹的猜想,我可以想象它会以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;
  ...
}