\documentclass[]{article}
\usepackage{amsmath,graphicx,supertabular,hyperref,tabularx,ifthen}
\title{TIP \#313: Inexact Searching in Sorted List}
\date{February 14, 2008}
\author{Peter Spjuth}
\urlstyle{sf}
\setlength{\parskip}{1ex}
\setlength{\parindent}{0pt}
\def\tipversion$#1${\texttt{\$#1\$}}
\def\tiplangle#1{\ensuremath{<}}
\def\tiprangle#1{\ensuremath{>}}
\def\tipbar#1{\ensuremath{|}}
\def\tipmail#1#2{\(\langle\){\small\expandafter\url{#1@#2}}\(\rangle\)}
\ifx\pdfoutput\undefined
\newcommand{\tipimage}[2]{\typeout{Make sure you download #1.eps}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.eps}}{\includegraphics[width=0.8\textwidth]{#1.eps}}}
\newcommand{\tipxref}[1]{}
\newcommand{\tipxrefend}{}
\else
\newcommand{\tipimage}[2]{\typeout{Make sure you create #1.pdf}\ifthenelse{\lengthtest{0.8\textwidth>#2}\and\lengthtest{0pt<#2}}{\includegraphics{#1.pdf}}{\includegraphics[width=0.8\textwidth]{#1.pdf}}}
\pdfcatalog{/PageMode /UseOutlines}
\newcommand{\tipxref}[1]{\pdfannotlink attr {/C [0.5 0.5 1.0] /Border [0 0 1]} goto name {#1}}
\newcommand{\tipxrefend}{\pdfendlink}
\fi
\newenvironment{tipabstract}{\begin{abstract}}{\end{abstract}}
\begin{document}\maketitle
\begin{center}\begin{tabularx}{\linewidth}{|r@{: }X|}\hline
\textbf{TIP \#313}&\textbf{Inexact Searching in Sorted List}\\\hline
Author&

Peter Spjuth \tipmail{peter.spjuth}{gmail.com}
\\
Created&Thursday, \(\text{14}^{\text{th}}\) February 2008\\
Type&Project\\
Tcl Version&\(8.6\)\\
State&Final\\
Vote&Done\\
Version&\tipversion$Revision: 1.14 $\\
Keywords&Tcl\\
Post History&\\
\hline\end{tabularx}\end{center}
\thispagestyle{empty}\pagestyle{empty}
\begin{tipabstract}

This TIP adds a new switch to \textbf{lsearch} to do a binary search to find the insertion point in a sorted list.
\end{tipabstract}
\tableofcontents\setcounter{page}{0}\clearpage\pagestyle{plain}

\section{Rationale}

Sometimes, it is necessary to find the location in a sorted list where a particular new element could be inserted. Either for actual insertion or for lookups to do interpolation or approximate search in data tables. Given that the list is already sorted, it is obviously the case that the location should be located through an O(log N) algorithm that takes advantage of this fact (binary searching is the most reliable method given that measuring the ``distance'' between two strings is a complex and expensive operation in itself).

The usefulness of the feature is shown by a quick search. I found usages in the core, in tcllib and in tklib. Given that the infrastructure for a binary search is already in \textbf{lsearch}, this is a very cheap addition.

One question for the specification is exactly what index should be returned. Below an increasing list is assumed, things are equivalent for a decreasing.
\begin{enumerate}
\item{}
First where element is greater than key.
\setcounter{enumi}{1}
\item{}
Last where element is less than or equal to key.
\setcounter{enumi}{2}
\item{}
First where element is greater than or equal to key.
\setcounter{enumi}{3}
\item{}
Last where element is less than key.
\end{enumerate}

Here, 1 is the use case for a stable insertion sort.

In the core we can find \textbf{::tcl::clock::BSearch} which returns the index of the greatest element in \$list that is less than or equal to \$key, i.e. type 2. The same can be found in tklib's ::khim::BSearch.

In tcllib we can find \textbf{::struct::prioqueue::\_\_linsertsorted}, which would use type 1.

Personally I have had use for both 2 and 3.

1 can trivialy be calculated from 2 and vice versa. Same for 3 and 4.

One key difference between 1/2 and 3/4 is that 1/2 return last among equals while 3/4 returns first among equals. This means that it is easier to lay 3/4 over 1/2 by first doing an exact search. \textit{i.e.} by doing both a -sorted and a -bisect search you get all info needed, in log(N) time, to get either of 1/2/3/4.

Finally, I think it makes sense for \textbf{lsearch} to return an exact match if there is one, leading to type 2 being specified in this TIP.

For a decreasing list, things are equivalent. The same relationships between 1/2/3/4 applies, so it is reasonable to select the same there.

I saw the word bisect used for this type of operation, but a better name is probably possible if someone have a suggestion.

\section{Specification}

An option \textbf{-bisect} is added to \textbf{lsearch}. This is a modifier to \textbf{-sorted} and implies \textbf{-sorted} search mode.

The list to be searched thus must be sorted and how it is sorted is specified just as for unmodified \textbf{-sorted}.

For an increasing list, the \textbf{-bisect} flag makes \textbf{lsearch} return the greatest index where the element is less than or equal to the key.

For a decreasing list, the \textbf{-bisect} flag makes \textbf{lsearch} return the greatest index where the element is greater than or equal to the key.

If the key is before the first element, or the list is empty, -1 is returned.

It is illegal to use \textbf{-bisect} with either \textbf{-all} or \textbf{-not}.

Note that \textbf{-inline} and \textbf{-start} are still valid, though perhaps not very useful.

\section{Examples}

A stable insertion sort:
\begingroup\small\begin{verbatim}
set dest {}
foreach elem $src {
    set i [lsearch -bisect -integer $dest]
    set dest [linsert $dest [+ $i 1] $elem]
}
\end{verbatim}
\endgroup

\section{Reference Implementation}

\url{http://sourceforge.net/support/tracker.php?aid=1894241}

\section{Further Use Cases}

Some messages on \url{news:comp.lang.tcl} provide additional motivation for this TIP:

From Kevin Kenny: \tipmail{47B59A43.9040205}{acm.org}:

\begin{quote}
[...] When I've coded binary search like that, it's generally been as part of an interpolation or approximate search procedure. For instance, \textbf{::tcl::clock::BSearch} finds, among other things, the last change of time zone at or before a given time. The cubic spline procedure in tcllib uses BSearch to find the control point just to the left of the interpolated point. There are a great many cases where you want to look up the nearest neighbour without inserting anything if there is no exact match.
\end{quote}

From Neil Madden: \tipmail{fp46r6\$pb6\$1}{oyez.ccc.nottingham.ac.uk}:

\begin{quote}
Indeed. My own recent experience was in looking up annotations to display while playing back some 3D visualisation data (through Togl). A list of form \{timestamp annotation ts annot ...\} was used and the annotation should be displayed for any frame from that timestamp up until the next annotation. When the user can randomly seek to any position in the data it was necessary to find the nearest preceeding annotation. I hand-coded a binary search for this. This \textbf{lsearch} enhancement would have been ideal (well, providing I massaged the data into a form suitable for use with \textbf{-index}, which I assume this TIP is compatible with).
\end{quote}

\section{Alternatives}

Instead of making \textbf{-bisect} a modifier to \textbf{-sorted} it could be a search mode in itself. This was the original specification in this TIP. Making it a modifier makes more sense and makes documentation simpler.

\subsection{Discussion: Alternative Names}

Naming the option based on something like ``insert'', like \textbf{-insertpos} or making this an option to \textbf{linsert}; Since the spec selects variant 2, it does not return the actual insertion position.

The name \textbf{-nearest} was proposed. Since the spec does not return the nearest, it is not that good.

Also proposed was ``\textbf{-inexact} (by analogy with switch -exact).'' ``\textbf{-inexact} is good enough for the title of the TIP, so it should be good enough for the option name. It may be tricky writing the documentation since \textbf{-sorted} already implies \textbf{-exact}.''

``Names that capture the meaning better are too verbose, but maybe they'll suggest a good name ... -allowmissing -maybeabsent -absent -approximate -fuzzy -insertionpointifmissing''

``The difference with the new option is that the search term need not be present in the list. That distinction is what the option name should capture.''

\section{Copyright}

This document has been placed in the public domain.

\section{Colophon}

\textit{TIP AutoGenerator --- written by Donal K. Fellows}
\end{document}
