Xml binary search through attributes

Question

I have an xml document which contains tags with numerical attribute. They are sorted by this attribute. is it worth to finding this tags through binary search? Or access to the nodes are not in constant time and it is better to get the data to array? And is it implemented in xml libraries?

Answer 1

It depends how are you planing to read the document. There are two ways to handle XML documents:

First one, implemented by XmlReader, is stream-oriented and processes one element at a time, and nothing more is stored in program memory.

Second one follows Document Object Model interface: it loads the entire document into memory and allows you to query it without looking back to the file. The best method to use that in .NET is LINQ to XML.

Depending of the size of your document, it may be better to choose one or another, but you have to be aware that making any other then linear search with Stream-oriented API is not possible.

And as far I know there you can't get binary search with LINQ to XML out of the box, because it uses IEnumerable. You'd have to get an array of your elements and then implement the binary search on an array. Definitely not difficult task to complete anyway.