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

Question

我正在使用Tcl。我有一個排序的實數列表。鑑於數n我需要找到它是列表元素的索引：

• 等於或者少n;
• 或大於n。

有沒有什麼標準的方法來做到這一點？ lsearch預計完全匹配並且不能使用。

Answer 1

與TCL 8.6（仍處於測試階段）lsearch會做什麼你問的-sorted和新-bisect選項允許如下：

-bisect
不精確搜索時，列表中的元素都在有序。對於遞增列表，返回元素小於 或等於該模式的最後一個索引。對於遞減列表，其中元素大於或等於該模式的最後一個 索引是 返回。

爲TCL之前的版本8.6你將不得不推出自己的代碼，因爲該列表進行排序，應該是相當簡單寫有您需要的屬性二進制搜索，羅塞塔代碼here包含純二分搜索的描述以及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"