ArrayList二分查找

Question

我正忙于为MCTS 70-536考试做准备。根据考试书籍（Microsoft Press - .NET Framework - Application Development Foundation Self Paced Training Kit 2nd Edition）的说法，这段代码示例：

ArrayList al = new ArrayList();
al.AddRange(new string[] { "Hello", "world", "this", "is", "a", "test" });
Console.WriteLine(al.BinarySearch("this"));

将值“2”输出到控制台，因为项“this”位于索引2。同意当我运行该代码时，这是我得到的输出。

但是如果我运行

Console.WriteLine(al.BinarySearch("world"));

我本来期望控制台输出的值是1，因为'world'应该在索引1上，但实际得到的却是-7?

请问有人能解释一下这是怎么回事吗？

谢谢

- Kevin McKelvin

Answer 1

你正在执行二分搜索的数组没有被排序。这是BinarySearch所需的一个条件。

由于未排序，会混淆搜索算法，并使其认为“world”应该在第7个位置，但实际上它不在数组中：结果为-7。

- GvS

---

谢谢，这给了我更好的结果。我对书中的错误感到非常惊讶。.BinarySearch(s)和.IndexOf(s)方法做同样的事情听起来有点奇怪。 - Kevin McKelvin

Answer 2

直接摘自ArrayList.BinarySearch的MSDN文档（http://msdn.microsoft.com/en-us/library/5tzt7yz3%28VS.85%29.aspx）

值参数和ArrayList中的每个元素都必须实现IComparable接口，用于比较。ArrayList中的元素必须按照IComparable实现定义的排序顺序按递增值排序;否则，结果可能不正确。

- wasatz

Answer 3

问题已经得到解答，但为了参考而添加此内容。

二分查找将使用排序算法查找项目。在您的示例中，默认排序是按字母顺序排列的，因此“world”应该是最后一个，因此是第7个。

您将看到BinarySearch的重载程序接受一个IComparer对象。不提供这个对象会给出默认的字母顺序排序。

但是，如果您按照书中建议实现了“reverseSort”方法，则需要将“reverseSort”对象传递给BinarySearch函数。

像这样：

Console.WriteLine(al.BinarySearch(al, new reverseSort()));

另外，如果你实现了“reverseSort”类并在哪些值被比较时进行控制台输出，我发现这非常有趣，但结果并不符合我的预期。我花了一点时间来研究算法是什么。

- Mike Mengell

Answer 4

来自文档：

如果找到value，则为排序后ArrayList中的基于零的索引；否则为负数，它是大于value的下一个元素的索引的按位补码，如果没有更大的元素，则为Count的按位补码。

请注意sorted这个词。

- Darin Dimitrov