在Tcl中搜索排序列表中的数字

Question

我正在使用Tcl.我有一个实数的排序列表.给定数字n我需要找到list元素的索引,它是:

• 要么少于等于n;
• 或大于n.

有没有标准的方法来做到这一点？lsearch期望完全匹配,不能使用.

Answer 1

使用Tcl 8.6(仍处于测试阶段),lsearch将执行您的要求,-sorted新-bisect选项允许以下内容:

-bisect
列表元素按排序顺序时不精确搜索.对于增加的列表,返回元素小于或等于模式的最后一个索引.对于递减列表,返回元素大于或等于模式的最后一个索引.

对于8.6之前的Tcl版本,您必须滚动自己的代码,鉴于列表已排序,使用您需要的属性编写二进制搜索应该相当简单,此处的 Rosetta代码包含纯二进制搜索的描述还有一个Tcl实现.您应该可以将此作为起点.

这是我创建的一个非常快速的版本,它返回您搜索的值的索引或大于它的值.要注意的例外是列表的结尾,搜索超出最大元素的值将返回最大元素.它只进行了最低限度的测试,所以如果您使用它,请做一些额外的测试!如果搜索找到值,我也不会停止,如果这可能经常发生,您可能希望针对此进行优化.

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"