A small algorithm to find the index of the first element superior or equal to the given value. The given sequence must be ordered. This tail recursive algorithm is inspired by the binary search algorithm.
#!/bin/sh
exec scala "$0" "$@"
!#
import scala.annotation.tailrec
// ---------------------------------------------------
def searchFirstGreaterOrEqual[T<%Ordered[T]](seq: Seq[T], value: T):Option[Int] = {
@tailrec
def binarysearch(left:Int, right:Int):Option[Int] = {
if (seq(left)>=value) Some(left)
if (seq(right)<value) None // Not found
else {
(left+right)/2 match {
case m if seq(m)==value => Some(m)
case m if seq(m)>value =>
if (m!=left) binarysearch(left, m) else Some(m)
case m if seq(m)<value =>
if (m<right) binarysearch(m+1, right)
else None // Not found
}
}
}
binarysearch(0, seq.size-1)
}
// ---------------------------------------------------
val l1=List(10,20,30,50,100)
def testWith[T<%Ordered[T]](seq:Seq[T], value:T) {
val result = searchFirstGreaterOrEqual(seq, value)
println(s"${value}->${result}")
}
println(s"""Results with ${l1.mkString(" ")}""")
testWith(l1, 0)
testWith(l1, 15)
testWith(l1, 20)
testWith(l1, 55)
testWith(l1, 150)