我正在尝试在Scala中实现searchsorted算法(side = right),即找到应该在其中插入元素以维持排序顺序的最后一个索引。
对于前。
val arr = List(1,2,2,3,4,4,6,6). // assume list is sorted, also array can have negetive elements(albeit sorted)
if elem = 2, output index = 3
if elem = 3, output index = 4
if elem = 5, output index = 6
if elem = -3, output index = 0
我想到了这一点,遍历列表中的每个元素,并检查最小的差异
val a = List(1,1,2,2,3,3,4,5,5)
val elem = 1
val (_, index) = a
.foldLeft(Int.MaxValue, 0) {
case ((smallestDiff, index), currNum) =>
val currDiff = (elem - currNum).abs
if (currDiff > smallestDiff) (smallestDiff, index)
else (currDiff, index + 1)
}
这对于1st 2个示例正常工作,但对于最后2个ex则完全中断
indexWhere()
可以完成大部分繁重的工作。
def insertHere(ns:Seq[Int], elem:Int):Int = {
val idx = ns.indexWhere(_ > elem)
if (idx < 0) ns.length
else idx
}
insertHere( List(1,2,2,3,4,4,6,6), 2) // 3
insertHere( Seq(1,2,2,3,4,4,6,6), 3) // 4
insertHere( Array(1,2,2,3,4,4,6,6), 5) // 6
insertHere(Vector(1,2,2,3,4,4,6,6),-3) // 0
insertHere( List(1,2,2,3,4,4,6,6),12) // 8
当elem
应在末尾附加时,这将返回不存在的索引。