TIP #313 Version 1.1: Inexact Searching in Sorted List

This is not necessarily the current version of this TIP.

Abstract

This TIP adds a new switch to lsearch to do a binary search to find the insertion point in a sorted list.

Rationale

Sometimes, it is necessary to find the location in a sorted list where a particular new element should be inserted. Given that the list is already sorted, it is obviously the case that the location should be located through an O(ln 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 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.

1. First where element is greater than key.

2. Last where element is less than or equal to key.

3. First where element is greater than or equal to key.

4. Last where element is less than key.

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

In the core we can find ::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 ::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.