Binary search a list of objects

[Tom Ruby]

I have a list of "components" like so:

public class Component
{
public string Name { get; set; }
public string id { get; set; }
public string TestValue { get; set; }
public string OrigValue { get; set; }
public bool Found;
};

List<Component> ComponentList = new List<Component>()
{
new Component(){Name="Nitrogen", id="N2", TestValue="60.38", OrigValue="", Found=false},
new Component(){Name="Methane", id="C1", TestValue="76.01", OrigValue="", Found=false},
new Component(){Name="Carbon Dioxide", id="CO2", TestValue="138.42", OrigValue = "", Found=false},
new Component(){Name="Ethylene", id="C2=", TestValue="145.32", OrigValue = "", Found=false},
new Component(){Name="Ethane", id="C2", TestValue="125.20", OrigValue="", Found=false},
new Component(){Name="Propane", id="C3", TestValue="70.25",OrigValue="", Found=false},
new Component(){Name="Isobutane", id="IC4", TestValue="107.07", OrigValue="", Found=false},
new Component(){Name="Normal Butane", id="NC4", TestValue="120.15", OrigValue="", Found=false},
new Component(){Name="Neopentane", id="NeoC5", TestValue="154.95", OrigValue="", Found=false},
new Component(){Name="Isopentane", id="IC5", TestValue="205.80", OrigValue="", Found=false},
new Component(){Name="Normal Pentane", id="NC5", TestValue="15.95", OrigValue="", Found=false},
new Component(){Name="Hexane Plus", id="C6+", TestValue="31.85", OrigValue="", Found=false},
new Component(){Name="Hexanes", id="C6s", TestValue="117.75", OrigValue="", Found=false},
new Component(){Name="Heptanes", id="C7s", TestValue="69.35", OrigValue="", Found=false},
new Component(){Name="Octanes", id="C8s", TestValue="129.45", OrigValue="", Found=false},
new Component(){Name="Nonanes", id="C9s", TestValue="73.51", OrigValue="", Found=false},
new Component(){Name="Decanes", id="C10s", TestValue="49.57", OrigValue="", Found=false},
new Component(){Name="Undecanes", id="C11s", TestValue="98.26", OrigValue="", Found=false},
new Component(){Name="Ethylene Minus", id="C2-", TestValue="132.25", OrigValue="", Found=false},
new Component(){Name="Propane Plus", id="C3+", TestValue="86.75", OrigValue="", Found=false},
new Component(){Name="Hydrogen Sulfide", id="H2S", TestValue="73.62", OrigValue="", Found=false},
new Component(){Name="Water", id="H2O", TestValue="26.12", OrigValue="", Found=false},
new Component(){Name="Helium", id="He", TestValue="19.56", OrigValue="", Found=false},
new Component(){Name="Hydrogen", id="H2", TestValue="38.67", OrigValue="", Found=false}
};


And I'll have to retrieve each of these in a loop, fiddling the members. Using a foreach loop results in an order N^2 operation, which is slower than I'd like. An order N log(N) operation seems much nicer.

I see that my list has a Binary Search method that returns an index. "Just what I need!"

So, I sorted my list:

ComponentList.Sort(delegate (Component x, Component y)
{
return x.Name.CompareTo(y.Name);
});

That was easy.

Hmm. Looking for an example of how to binary search on a member. Before I code up my own, is there a similar graceful way to binary search this? I'm thinking of something on the order of:

int i = ComponentList.BinarySearch("Plutonium", delagate(Component x, Component y)
{
return x.Name.CompareTo(y.Name)
});

But, of course, the delegate trick that works for sort doesn't work for search.

Continue reading...