ArrayList.BinarySearch problem

[Eric Eggermann]

I'm going batty trying to figure out why this is not working.

I'm trying to find all objects within a class derived from CollectionBase
which meet a certain criteria, but the search seems to be skipping some
objects. The following code is supposed to start searching the InnerList
from the beginning, and continue searching while there are still objects
that my comparer class says matches. In the code, comp is my comparer
object, and source is the object I'm looking for.

int from = 0;
int pos = 0;
while(pos >= 0)
{
pos = InnerList.BinarySearch(from, InnerList.Count - from, source,
comp);
if(pos > -1)
{
//.....Do some stuff with the object at index pos....
from = pos + 1;
}
}

Now with my test, if there is one object in the collection, it works. I get
that object. But if there is more than one, I don't get all. With the test
case of five objects, I get three, the first two are skipped over. I checked
and found that my comparer is not being called five times. The documentation
states that if BinarySearch finds more than one match, it only returns the
first one. This is not what I am seeing. It seems to be skipping over the
first two objects in my collection, based on the fact that my comparer is
only being called three times, while searching through 5 objects, all of
which should be hits. If I iterate through the collection, calling my
comparer myself, all five return tests return 0 as expected.

I'm not particularyly averse to writing my own search but I'd like to
understand why I don't see the documented behavior. Any ideas?

Eric

 

[Jon Skeet [C# MVP]]

<"Eric Eggermann" <<none>>> wrote:

Now with my test, if there is one object in the collection, it works. I get
that object. But if there is more than one, I don't get all. With the test
case of five objects, I get three, the first two are skipped over. I checked
and found that my comparer is not being called five times. The documentation
states that if BinarySearch finds more than one match, it only returns the
first one. This is not what I am seeing. It seems to be skipping over the
first two objects in my collection, based on the fact that my comparer is
only being called three times, while searching through 5 objects, all of
which should be hits. If I iterate through the collection, calling my
comparer myself, all five return tests return 0 as expected.

It sounds like your comparer isn't being terribly useful. Note that:

<quote>
If the ArrayList contains more than one element with the same value,
the method returns only one of the occurrences, and it might return any
one of the occurrences, not necessarily the first one.
</quote>

So there's nothing to stop it from returning the last element, and
that's all.

If your comparer is just returning 0 for everything, I'd just iterate
over the whole collection if I were you. BinarySearch is for *sorted*
lists where there's a meaningful comparison to make.

 

[Eric Eggermann]

Where did you find that quote about it returns any one of the ocurrences? My
help file states "If the ArrayList contains more than one element with the
same value, the method returns only the index of the first occurrence."
Of course, your quote explains what I'm seeing perfectly. My doc should
probably read 'returns the index of the first occurrence found'. And
actually, my collection is sorted, and the comparer is doing exactly what I
need it to do. The objects all contain different values, but within this
program, many will be considered the same.

Anyway, thanks for that quote Jon, I'll have to write my own search. I'd
have liked to have avoided that, but there's nothing else for it.

Cheers,
Eric

 

[Jon Skeet [C# MVP]]

Where did you find that quote about it returns any one of the ocurrences?

The docs for ArrayList.BinarySearch Method (Int32, Int32, Object,
IComparer) in the remarks. The other overloads have the same bit in.

My help file states "If the ArrayList contains more than one element with the
same value, the method returns only the index of the first occurrence."

Hmm... odd.

Of course, your quote explains what I'm seeing perfectly. My doc should
probably read 'returns the index of the first occurrence found'. And
actually, my collection is sorted, and the comparer is doing exactly what I
need it to do. The objects all contain different values, but within this
program, many will be considered the same.

Anyway, thanks for that quote Jon, I'll have to write my own search. I'd
have liked to have avoided that, but there's nothing else for it.

Well, if your list is sorted, then you just need to find *a* match, and
then go each way (forwards and backwards) until it doesn't match. As
it's already sorted, all the matches should be in one "lump" as it
were.

 

[Guest]

do you know what the binary search algorithm does? the behavior you are experiencing is exactly what one would expect from a binary search. binary search always start at the middle of the list, keeps on cutting list in half until a match is found. so stepping through your code, the very first match is found at pos 2 since that's the middle of the list. first 2 elements are skipped by your own code because from = pos + 1

----- Eric Eggermann > wrote: ----

I'm going batty trying to figure out why this is not working

I'm trying to find all objects within a class derived from CollectionBas
which meet a certain criteria, but the search seems to be skipping som
objects. The following code is supposed to start searching the InnerLis
from the beginning, and continue searching while there are still object
that my comparer class says matches. In the code, comp is my compare
object, and source is the object I'm looking for

int from = 0
int pos = 0
while(pos >= 0

pos = InnerList.BinarySearch(from, InnerList.Count - from, source
comp)
if(pos > -1

//.....Do some stuff with the object at index pos...
from = pos + 1



Now with my test, if there is one object in the collection, it works. I ge
that object. But if there is more than one, I don't get all. With the tes
case of five objects, I get three, the first two are skipped over. I checke
and found that my comparer is not being called five times. The documentatio
states that if BinarySearch finds more than one match, it only returns th
first one. This is not what I am seeing. It seems to be skipping over th
first two objects in my collection, based on the fact that my comparer i
only being called three times, while searching through 5 objects, all o
which should be hits. If I iterate through the collection, calling m
comparer myself, all five return tests return 0 as expected

I'm not particularyly averse to writing my own search but I'd like t
understand why I don't see the documented behavior. Any ideas

Eri

 

[mikeb]

The docs for ArrayList.BinarySearch Method (Int32, Int32, Object,
IComparer) in the remarks. The other overloads have the same bit in.




Hmm... odd.

The docs for Framework 1.0 state that the index of the first occurrence
will be returned.

This was changed in the 1.1 docs to say that the index returned would
not necessarily be the first if there were more than one element with
the same value.

It appears that the 1.0 docs are in error.

 

[Eric Eggermann]

Yeah, sure, I knew how it works, just my docs said they returned the first,
so silly me, I thought that's what it did. My docs are old I guess. I just
figured it did the backup down the list to find the first for me. My mistake
was assuming my code was wrong, instead of the docs.

Thanks for the help, all. I got it now.

Eric

do you know what the binary search algorithm does? the behavior you

are experiencing is exactly what one would expect from a binary search.
binary search always start at the middle of the list, keeps on cutting list
in half until a match is found. so stepping through your code, the very
first match is found at pos 2 since that's the middle of the list. first 2
elements are skipped by your own code because from = pos + 1.