BUG: ArrayList BinarySearch

[Homa]

I can' believe my own eye, but it happens...there is a bug in
ArrayList.BinarySearch!! It should be such a simple function......

Here is the detail. (I'm using C#, don't know if this is C#'s problem
or the whole framework's problem.

ArrayList test = new ArrayList();

test.Add(10);
test.Add(7);
test.Add(2);

test.BinarySearch(10);

the Search would return -4 instead of 0!! When you debug it, you see
in the variable test is normal:

test[0] = 10, test[1] = 7, test[2] = 2.

Who wrote this function..........

Homa Wong

 

[Jay B. Harlow [MVP - Outlook]]

Homa,
In order for the BinarySearch to work, you need to have a Sorted list!

As by definition a binary search can only search sorted values!

For details see:
http://msdn.microsoft.com/library/d...ollectionsArrayListClassBinarySearchTopic.asp

Which states "Uses a binary search algorithm to locate a specific element in
the sorted ArrayList". Notice the word sorted in there!

Seeing as your list is sorted in descending order, you will need to use the
overloaded BinarySearch function that accepts a Comparer object that does
descending comparisons, as the default comparison will do ascending
comparisons!

Hope this helps
Jay

 

[Mattias Sjögren]

I can' believe my own eye, but it happens...there is a bug in
ArrayList.BinarySearch!!

No there isn't. The list must be sorted (in ascending order), but
yours obviously isn't.



Mattias

 

[William Ryan]

Homa:

No, it's not bug. Binary Searches depend on a Sorted List, and in your
example, it's not sorted. As such, you'll get weird behavior and that's
well documented and not a bug. The whole concept of a Binary search is
built upon ordering, how else coudl you divide and conquer like it does?

Sort your list and it works fine.

http://msdn.microsoft.com/library/d...ollectionsarraylistclassbinarysearchtopic.asp

The first line in the documentation makes this pretty clear


HTH,

Bill

 

[Homa]

I'm so sorry. I can't believe myself.....sigh...

Thankyou,

Homa Wong

Homa:

No, it's not bug. Binary Searches depend on a Sorted List, and in your
example, it's not sorted. As such, you'll get weird behavior and that's
well documented and not a bug. The whole concept of a Binary search is
built upon ordering, how else coudl you divide and conquer like it does?

Sort your list and it works fine.

http://msdn.microsoft.com/library/d...ollectionsarraylistclassbinarysearchtopic.asp

The first line in the documentation makes this pretty clear


HTH,

Bill

I can' believe my own eye, but it happens...there is a bug in
ArrayList.BinarySearch!! It should be such a simple function......

Here is the detail. (I'm using C#, don't know if this is C#'s problem
or the whole framework's problem.

ArrayList test = new ArrayList();

test.Add(10);
test.Add(7);
test.Add(2);

test.BinarySearch(10);

the Search would return -4 instead of 0!! When you debug it, you see
in the variable test is normal:

test[0] = 10, test[1] = 7, test[2] = 2.

Who wrote this function..........

Homa Wong