Searching for a number in a sorted list in Tcl

Question

I'm using Tcl. I have a sorted list of real numbers. Given the number n I need to find an index of the list element which is:

• either less of equal to n;
• or greater than n.

Is there any standard way to do this? lsearch expects exact match and can't be used.

Answer 1

With Tcl 8.6 (still in beta) lsearch will do what your asking, the -sorted and new -bisect options allow the following:

-bisect
Inexact search when the list elements are in sorted order. For an increasing list the last index where the element is less than or equal to the pattern is returned. For a decreasing list the last index where the element is greater than or equal to the pattern is returned.

For Tcl versions prior to 8.6 your going to have to roll your own code, given that the list is sorted it should be fairly straightforward to write a binary search with the properties that you require, Rosetta code here contains a description of a pure binary search and also a Tcl implemention. You should be able to use this as your starting point.

Here is a very quick version I created, it returns the index of either the value you search for or the value greater than it. The exception to watch for is the end of the list, searching for a value beyond the largest element returns the largest element. It's only had minimal testing so if you do use it do some additional tests! I also don't stop if the search finds the value, if this is likely to happen often you may want to optimize for this.

set lst [lsort -real [list 1.2 3.4 5.4 7.9 2.3 1.1 0.9 22.7 4.3]]
puts $lst

# Assumes that lst is sorted in ascending order
proc bisect { lst val } {

    puts "Looking for $val in $lst"

    set len [llength $lst]

    # Initial interval - the start to the middle of the list
    set start 0
    set end [expr $len - 1]
    set mid [expr $len / 2]
    set lastmid -1

    while { $mid != $lastmid } {
        if { [expr $val <= [lindex $lst $mid]] } {
            # val lies somewhere between the start and the mid
            set end $mid

        } else {
            # val lies somewhere between mid and end
            set start [expr $mid + 1]
        }

        set lastmid $mid
        set mid [expr ($start + $end ) / 2]
    }

    return $mid
}

set res [bisect $lst 2.4]
puts "found [lindex $lst $res] at index $res"

set res [bisect $lst -1]
puts "found [lindex $lst $res] at index $res"

set res [bisect $lst 999]
puts "found [lindex $lst $res] at index $res"

set res [bisect $lst 1.2]
puts "found [lindex $lst $res] at index $res"

set res [bisect $lst 0.9]
puts "found [lindex $lst $res] at index $res"

set res [bisect $lst 22.7]
puts "found [lindex $lst $res] at index $res"