ArrayList BinarySearch

Question

Hi there

I'm busy preparing for the MCTS 70-536 exam, according to the exam book (Microsoft Press - .NET Framework - Application Development Foundation Self Paced Training Kit 2nd Edition), this code sample:

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

Outputs the value '2' to the console because the item 'this' is at index 2. Agreed that is the output I get when I run that code.

However if I run

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

I would expect to get the value 1 in the console since 'world' would be at index 1, however I get the value -7 ?

Could anyone please explain how this works?

Thanks

Answer 1

The array you are performing the binary search on is not sorted. This is a requirement for BinarySearch to function.

Being not sorted, confuses the search algorithm, and makes it think that "world" should be on the 7th place, but it is not in the array: the result is -7.

Answer 2

Taken directly from MSDN documentation of ArrayList.BinarySearch (http://msdn.microsoft.com/en-us/library/5tzt7yz3%28VS.85%29.aspx)

The value parameter and each element of the ArrayList must implement the IComparable interface, which is used for comparisons. The elements of the ArrayList must already be sorted in increasing value according to the sort order defined by the IComparable implementation; otherwise, the result might be incorrect.

Answer 3

From the documentation:

The zero-based index of value in the sorted ArrayList, if value is found; otherwise, a negative number, which is the bitwise complement of the index of the next element that is larger than value or, if there is no larger element, the bitwise complement of Count.

Notice the sorted word.