how to do Generic.List.BinarySearch on byRef data?

  • Thread starter Thread starter Buky
  • Start date Start date
B

Buky

So, Let's say that I have an class with properies like Name, LastName & ID.
I put them into List(of myClass) and I would like to search through that
List based on my search criteria (Name & Id for example).
So, I create an Comparer, and provide it's 'reference' to an BinarySearch
functio, but each time I got incorrect results.
Where could be problem in following code?

Public Class myClass
Public Id As Int32
Public Name As String
Public LastName As String

Public Sub New()
End Sub
Protected Overrides Sub Finalize()
MyBase.Finalize()
End Sub
End Class

Public Sub test_novi()
Dim Lista As New List(Of myClass)
Dim y As Int32
Dim C As IComparer(Of MyClass)
C = New MyCompare
Dim T As New MyClass

T.Id = 1
T.Name = 2
Lista.Add(T)
T = New MyClass
T.Id = 2
T.Name = 4
Lista.Add(T)
T = New MyClass
T.Id = 3
T.Name = 6
Lista.Add(T)

Lista.Sort()
Dim T1 As New MyClass
T1.Id = 1
T1.Name = 2

y = Lista.BinarySearch(T1, C)
End Sub
End Module

Public Class MyCompare
Implements IComparer(Of MyClass)
Public Sub New()
End Sub

Protected Overrides Sub Finalize()
MyBase.Finalize()
End Sub
Public Function Compare(ByVal x As MyClass,byVal y As MyClass) As
Integer Implements IComparer(Of MyClass).Compare
If x.Id = y.Id Then
If x.Name = y.Name Then
Return 0
Else
Return -1
End If
Else
Return -2
End If
End Function
End Class
 
Buky said:
So, Let's say that I have an class with properies like Name, LastName & ID.
I put them into List(of myClass) and I would like to search through that
List based on my search criteria (Name & Id for example).
So, I create an Comparer, and provide it's 'reference' to an BinarySearch
functio, but each time I got incorrect results.
Where could be problem in following code?
Click to expand...

Well:

1) BinarySearch only works if the list is already ordered to start
with, in an order which is consistent with the comparer you use.
2) Your comparer is inconsistent - in particular, if you do
Compare(x, y) and Compare(y, x) it could return a negative number
both times - meaning that x < y and y < x.
3) You appear to have finalizers for no reason, which is a generally
bad thing to do. (You also have public fields, but I'll assume
you wouldn't do that normally.)

If you make your comparer more sensible, and sort *passing in the
comparer* before calling BinarySearch it should work.
 
Jon Skeet said:
Well:

1) BinarySearch only works if the list is already ordered to start
with, in an order which is consistent with the comparer you use.
Click to expand...

does it means that I need to make some 'ordering' before binarySearch?
2) Your comparer is inconsistent - in particular, if you do
Compare(x, y) and Compare(y, x) it could return a negative number
both times - meaning that x < y and y < x.
Click to expand...

At this moment, it's not so important for me... I would like just to make it
work :(
3) You appear to have finalizers for no reason, which is a generally
bad thing to do. (You also have public fields, but I'll assume
you wouldn't do that normally.)
Click to expand...
yea, this is just an example...
If you make your comparer more sensible, and sort *passing in the
comparer* before calling BinarySearch it should work.
Click to expand...

I tried to call Sort sub before it, but it gave me an exception
(InvalidOperationException - failed to compare two elements in the array)
 
Buky said:
does it means that I need to make some 'ordering' before binarySearch?
Click to expand...

so that things are said:
At this moment, it's not so important for me... I would like just to make it
work :(
Click to expand...

Well it's important to the framework!

Think about it - binary searches only work if the items are in a
consistent order to start with. It's impossible for the items to *be*
in a consistent order when one item is simulataneously greater than and
less than another.
I tried to call Sort sub before it, but it gave me an exception
(InvalidOperationException - failed to compare two elements in the array)
Click to expand...

You need to pass in the IComparer<T> you're going to use for the binary
search, but it will need to be consistent.
 
Back
Top