BUG: ArrayList BinarySearch

  • Thread starter Thread starter Homa
  • Start date Start date
H

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
 
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
 
I can' believe my own eye, but it happens...there is a bug in
ArrayList.BinarySearch!!
Click to expand...

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



Mattias
 
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'm so sorry. I can't believe myself.....sigh...

Thankyou,

Homa Wong

William Ryan said:
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 said:
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
Click to expand...
Click to expand...
 
Back
Top