ArrayList BinarySearch

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 va开发者_开发技巧lue '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

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.

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.

Question already answered but added this for reference.

The BinarySearch will find items by using a sorted algorithm. In you example the default sort is alphabetical so "world" should be been last, hence number 7.

You will see an overloader of the BinarySearch which accepts an IComparer object. To not supply this gives the default sort of alphabetical.

But if you implemented the "reverseSort" method as the book suggests then you would need to pass the BinarySearch function the "reverseSort" object.

Like this;

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

Also just as I found it quite interesting if you implement the "reverseSort" class and do a console.writeline on which values get compared, the results weren't what I'd expect. I spent a little while trying to work out what the algorithm was.

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.