C# 二进制搜索返回负索引

Question

今天我已经把我的头放在二分搜索上。我听说这是在大数组中查找索引的最快方法。所以我决定编写代码，看看在没有我要搜索的索引的情况下是否会出现异常。

int[] longArray = new int[1000];
Random rnd = new Random();

for (int i = 0; i < longArray.Length; i++)
{
    longArray[i] = rnd.Next(1, 1000);
}

Array.Sort(longArray);            

int indexOfMyNum = Array.BinarySearch(longArray, 706);
Console.WriteLine("Here it is: " +  indexOfMyNum);

现在是有趣的部分，没有例外，我的程序总是返回数字，有时是负数。我知道随机不需要看到这种行为，但我想在更大的阵列上测试它。现在我的问题是，为什么我得到负索引而不是异常。如果我错了，请纠正我，因为数组的索引与内存地址直接相关，这是否意味着 BinarySearch 正在查看他不应该被允许的内存片段，看看我的号码是否在那里？

有人知道为什么会发生这种情况而不是例外吗？

Answer 1

方法文档解释了“奥秘”：

返回值

类型： System.Int32

指定数组中指定值的索引，如果找到值；否则为负数。如果未找到 value 并且 value 小于数组中的一个或多个元素，则返回的负数是大于 value 的第一个元素的索引的按位补码。如果未找到 value 并且 value 大于数组中的所有元素，则返回的负数是（最后一个元素的索引加 1）的按位补码。如果使用未排序的数组调用此方法，则返回值可能不正确并且可能返回负数，即使数组中存在值。（强调）

这意味着您的程序正在搜索数组中不存在的值，并获取插入位置的按位补码，即负数。

有人知道为什么会发生这种情况而不是例外吗？

坦率地说，发生这种情况是因为在集合中找不到项目并不是一种特殊情况。毕竟，我们经常寻找一个项目只是为了看看它是否在那里。BinarySearch返回负数的方法符合此要求，因为调用者可以始终判断该项目是否存在，如果不存在，插入的位置是什么：

int indexOfMyNum = Array.BinarySearch(longArray, 706);
if (indexOfMyNum < 0) {
    int insertionPos = ~indexOfMyNum;
    Console.WriteLine("The number is not there; insert at {0}", insertionPos);
}