ArrayList BinarySearch

Question

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

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.