|
Summary
This is an XSLT implementation of the traditional and very popular algorithm for searching in a sorted array.
This implementation is recursive and demonstrates the use of the "*" and "div" operators, as well as the "floor()" function.
We need to have a very efficient way of finding whether a particular object (a number, a string, a date,… etc.) belongs to a sorted set of (identically typed) objects. The only property these objects must have is a < relation, so that a set of them can be sorted and for any two objects a and b exactly one of the following holds true:
a
or
a = b
or
b
The idea is starting with the whole set to iteratively cut by half the interval to which the object belongs by comparing it to the middle element of the current interval (sorted subset) of elements. This is exactly the same algorithm we use every day when looking up a word in a dictionary.
It is straightforward to calculate the complexity of Binary Search – as a comparison is made for every half-interval searching for an element in a set of N elements will need not more than Log2(N) comparisons.
I used a traditional C implementation – the conversion to XSLT is almost straightforward. A recursively called named template has to be used as XSLT does not allow incrementing counters or changing the value of a variable. For reasons of simplicity I’m using numbers, but their values may hint us that these are actually dates.
The sorted structure, against which the algorithm will search is specified in the following source xml document:
<dates>
<date value=19271003/>
<date value=19321004/>
<date value=19530323/>
<date value=19640505/>
<date value=19920714/>
<date value=19990417/>
<date value=20001123/>
<date value=20010406/>
<date value=20020417/>
<date value=20100714/>
</dates>
The binSearch template has the following parameters:
<xsl:template name=binSearch> <xsl:param name=argNumber select=-Infinity/> <xsl:param name=nodeSet select=/../> <xsl:param name=First select=Infinity/> <xsl:param name=Last select=0/>
and their meaning is:
-
argNumber is the number to be searched for.
-
NodeSet is the node-set of sorted nodes, against which the search is performed.
-
First is the starting position of the interval of nodes against which the search is performed.
-
Last is the ending position of the interval of nodes against which the search is performed.
Note how the middle point is calculated:
<xsl:variable name=Mid select=floor(($First + $Last) div 2)/>
Apart from this the code should be quite easy to understand.
As its counterpart in other programming languages, this
implementation will be heavily used in other snippets implementing
many interesting and important algorithms. One is validation,
finding whether a given string belongs to a set of strings. Another
is sorting.
Here’s the complete stylesheet:
<xsl:stylesheet version=1.0
xmlns:xsl=http://www.w3.org/1999/XSL/Transform>
<xsl:output method=text/>
<xsl:variable name=theNumber select=20001123/>
<xsl:template match=/>
<xsl:call-template name=binSearch>
<xsl:with-param name=argNumber select=$theNumber/>
<xsl:with-param name=nodeSet select=dates/date/@value/>
<xsl:with-param name=First select=1/>
<xsl:with-param name=Last select=count(dates/date/@value)/>
</xsl:call-template>
</xsl:template>
<xsl:template name=binSearch>
<xsl:param name=argNumber select=-Infinity/>
<xsl:param name=nodeSet select=/../>
<xsl:param name=First select=Infinity/>
<xsl:param name=Last select=0/>
<xsl:choose>
<xsl:when test=$First > $Last>
-1
</xsl:when>
<xsl:otherwise>
<xsl:variable name=Mid select=floor(($First + $Last) div 2)/>
<xsl:choose>
<xsl:when test=$argNumber = $nodeSet[$Mid]>
<xsl:value-of select=$Mid/>
</xsl:when>
<xsl:when test=$argNumber < $nodeSet[$Mid]>
<xsl:call-template name=binSearch>
<xsl:with-param name=argNumber select=$argNumber/>
<xsl:with-param name=nodeSet select=$nodeSet/>
<xsl:with-param name=First select=$First/>
<xsl:with-param name=Last select=$Mid - 1/>
</xsl:call-template>
</xsl:when>
<xsl:when test=$argNumber > $nodeSet[$Mid]>
<xsl:call-template name=binSearch>
<xsl:with-param name=argNumber select=$argNumber/>
<xsl:with-param name=nodeSet select=$nodeSet/>
<xsl:with-param name=First select=$Mid + 1/>
<xsl:with-param name=Last select=$Last/>
</xsl:call-template>
</xsl:when>
<xsl:otherwise>
ERRROR
</xsl:otherwise>
</xsl:choose>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>
When applied on the source xml document above, it produces the correct result:
7
That is, 20001123 is the seventh in the sorted set represented by the source xml document.
| Further additional information | |
Updating comments...
Updating comments...
|
