Confusing Arraylist BinarySearch problem

J

Justin

Here's a quick rundown of what I'm doing.

I'm filling an arraylist with data. Then I loop through a dataset and grab
a field to perform a search on the arraylist. Every time I find a match I
update another field with a 1. If I don't find a match I update it with a
0. I then remove that item from the arraylist and move on. The end result
of this is I know which items ARE in the dataset, which items ARE NOT in the
dataset and which items do not BELONG in the dataset.

The problem I'm running into is when the arraylist contains items that are
not in the dataset. For some reason, during that scenario I get odd index
results when I search the arraylist.

Here's the arraylist (hardcoded for testing):
SAPArray.Add("004876497")
SAPArray.Add("48764205")
SAPArray.Add("48764212")
SAPArray.Add("48764229")
SAPArray.Add("48764236")
SAPArray.Add("48764243")
SAPArray.Add("48764250")
SAPArray.Add("48764267")
SAPArray.Add("48764274")
SAPArray.Add("48764281")
SAPArray.Add("48764298")
SAPArray.Add("48764304")
SAPArray.Add("48764311")
SAPArray.Add("48764328")
SAPArray.Add("48764335")
SAPArray.Add("48764342")
SAPArray.Add("48764359")
SAPArray.Add("48764366")
SAPArray.Add("48764373")
SAPArray.Add("48764380")
SAPArray.Add("48764397")
SAPArray.Add("11111111")
SAPArray.Add("222222222")
SAPArray.Add("3333333333")
SAPArray.Add("44444444444")
SAPArray.Add("555555555555")
SAPArray.Add("6666666666666")
SAPArray.Add("77777777777777")


The last 1-2-3-4-5-6-7 fields are purposely bogus.

Here's the resulting list I've created of the found index values when search
the arraylist for each one of these entries

004876497 0
48764205 0
48764212 0
48764229 0
48764243 1
48764236 0
48764366 -20
48764397 -20
48764380 -20
48764342 9
48764373 -19
48764304 5
48764359 8
48764335 7
48764250 0
48764274 1
48764328 4
48764311 3
48764281 1
48764298 -11
48764267 -11

A couple notes:
1. The last 1-2-3-4-5-6-7 fields don't show up because I only search based
on what's in the dataset and these do not apply.
2. It's possible to have duplicate index values because I'm removing the
found items as well.

What I don't understand, for example is that 48764366 has an index value
of -20 even though it is in fact in the arraylist. I also don't understand
what the difference is between the different negative values. Shouldn't a
null result just be -1?

My search string:
Dim index As Integer = SAPArray.BinarySearch(GetTagInfo(tags(i).TagID)(5),
New CaseInsensitiveComparer())


Any insight would be greatly appreciated!
 
J

Justin

We can even shorten up the issue. Let's say this is my array:

SAPArray.Add("04876497")
SAPArray.Add("48764205")
SAPArray.Add("48764212")
SAPArray.Add("48764229")
SAPArray.Add("48764236")
SAPArray.Add("48764243")
SAPArray.Add("48764250")
SAPArray.Add("48764267")
SAPArray.Add("48764274")
SAPArray.Add("48764281")
SAPArray.Add("48764298")
SAPArray.Add("48764304")
SAPArray.Add("48764311")
SAPArray.Add("48764328")
SAPArray.Add("48764335")
SAPArray.Add("48764342")
SAPArray.Add("48764359")
SAPArray.Add("48764366")
SAPArray.Add("48764373")
SAPArray.Add("48764380")
SAPArray.Add("48764397")
SAPArray.Add("11111111")
SAPArray.Add("22222222")
SAPArray.Add("33333333")
SAPArray.Add("44444444")
SAPArray.Add("55555555")
SAPArray.Add("66666666")
SAPArray.Add("77777777")

When I run this code directly after the array creation:
Dim index2 As Integer = SAPArray.BinarySearch("48764373", New
CaseInsensitiveComparer())
MsgBox(index2)

I get a negative value even though that item exists. For some reason
certain index values are more problematic them others. If I search for one
that's usual comes up good I get the proper index value.

But when I shorten my array to this:

SAPArray.Add("48764205")
SAPArray.Add("48764212")
SAPArray.Add("48764229")
SAPArray.Add("48764236")
SAPArray.Add("48764243")
SAPArray.Add("48764250")
SAPArray.Add("48764267")
SAPArray.Add("48764274")
SAPArray.Add("48764281")
SAPArray.Add("48764298")
SAPArray.Add("48764304")
SAPArray.Add("48764311")
SAPArray.Add("48764328")
SAPArray.Add("48764335")
SAPArray.Add("48764342")
SAPArray.Add("48764359")
SAPArray.Add("48764366")
SAPArray.Add("48764373")
SAPArray.Add("48764380")
SAPArray.Add("48764397")


I have no problems. The above code returns the proper index value.
 
H

Herfried K. Wagner [MVP]

Justin said:
We can even shorten up the issue. Let's say this is my array:

SAPArray.Add("04876497")
SAPArray.Add("48764205")
SAPArray.Add("48764212")
SAPArray.Add("48764229")
SAPArray.Add("48764236")
SAPArray.Add("48764243")
SAPArray.Add("48764250")
SAPArray.Add("48764267")
SAPArray.Add("48764274")
SAPArray.Add("48764281")
SAPArray.Add("48764298")
SAPArray.Add("48764304")
SAPArray.Add("48764311")
SAPArray.Add("48764328")
SAPArray.Add("48764335")
SAPArray.Add("48764342")
SAPArray.Add("48764359")
SAPArray.Add("48764366")
SAPArray.Add("48764373")
SAPArray.Add("48764380")
SAPArray.Add("48764397")
SAPArray.Add("11111111")
SAPArray.Add("22222222")
SAPArray.Add("33333333")
SAPArray.Add("44444444")
SAPArray.Add("55555555")
SAPArray.Add("66666666")
SAPArray.Add("77777777")

When I run this code directly after the array creation:
Dim index2 As Integer = SAPArray.BinarySearch("48764373", New
CaseInsensitiveComparer())
MsgBox(index2)

I get a negative value even though that item exists.
Click to expand...

Items must be sorted in order to search an item using binary search. You
can call the arraylist's 'Sort' method to sort it.
 
J

Justin

SAPArray.Sort()

Perfect! Thanks a bunch! I never knew that. I guess I've just been lucky
this whole time or something else was always sorting my data prior to
creation.

Am I to assume that once it hit where it thinks the value should be it stops
looking? If so then that's probably a huge speed increase in large array
scenarios.

Thanks again!


Thanks, Justin Emlay SAP Basis Administrator / Systems Department Maisto
International, Inc. 909-357-7988 ext.360 909-357-9958 fax (e-mail address removed)
www.maisto.com
 
Top