当找不到值时，C＃List .BinarySearch返回值

如果项目不存在，我对List的BinarySearch方法感到困惑。

我有

 List theList = {1, 3, 5, ...}. 

如预期的那样， theList.BInarySearch(0)返回0，而theList.BInarySearch(3)返回1。

但是， theList.BinarySearch(1)返回-2 ，而不是-1，正如我所期望的那样。 MSDN手册说：“返回值：如果找到项目，则排序列表中项目的从零开始的索引;否则，是负数，它是下一个元素的索引的按位补码，大于项目或，如果没有更大的元素，则为Count的按位补码。“

一个“按位补码”？ 我在这里错过了什么，为什么theList.BinarySearch(1) != -1 ？

Answer 1

首先 – 你为什么期望-1？ 如果该项目是第一个项目，则它不能返回-0 （对于整数），因此对于第二个项目将返回原因-2。

接下来，您可以使用~-2 – 按位运算符轻松获得正确的索引。

Answer 2

我假设您正在谈论theList.BinarySearch(2) ，因为1存在且返回值应为0 。

按位补码运算符不会产生与否定整数相同的效果，我认为这是你混淆的根源。 在任何情况下，您都不需要了解运算符如何准确地分支搜索结果; 你问题中的MSDN段落，以及~~a = a的事实直接暗示了这个片段：

 int index = theList.BinarySearch(num); if (index >= 0) { //exists ... } else { // doesn't exist int indexOfBiggerNeighbour = ~index; //bitwise complement of the return value if (indexOfBiggerNeighbour == theList.Count) { // bigger than all elements ... } else if (indexOfBiggerNeighbour == 0) { // smaller than all elements ... } else { // Between 2 elements int indexOfSmallerNeighbour = indexOfBiggerNeighbour - 1; ... } } 

Answer 3

返回这些否定索引的原因是支持将未找到的项插入到列表中。 在此示例中，将在index = 2处插入2。否则，您将不得不执行另一个二进制搜索以查找该位置。

Answer 4

要将其转换为插入点，请使用按位补码，即： ~retval