Search for a number in a sorted list in Tcl

Question

I am using Tcl. I have a sorted list of real numbers. Given the number n , I need to find the index of the list item, which:

• less than n ;
• or more n .

Is there a standard way to do this? lsearch expects an exact match and cannot be used.

Answer 1

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

-bisect
Inaccurate search when list items are sorted in sort order. For an ascending list, the last index where the element is less than or equal to the pattern. To reduce the list, the last index, where the element is greater than or equal to the pattern, is equal returned.

For versions of Tcl prior to 8.6, you will have to collapse your own code, given that the list is sorted, so you need to write a binary search with the properties you want, the Rosetta code here contains a description of a pure binary search, as well as an implementation of Tcl. You should use this as a starting point.

Here is a very quick version that I created, it returns the index of either the value you are looking for, or a value greater than it. An exception to viewing is the end of the list, looking for a value greater than the largest element returns the largest element. It had minimal testing, so if you use it, do some additional tests! I also do not stop if the search finds a value, if this can happen often, you can 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"