泛型不是那么通用!

Question

我尝试在 scala 中实现通用的二分搜索算法。这是:

type Ord ={
def <(x:Any):Boolean
def >(x:Any):Boolean
}
def binSearch[T <: Ord ](x:T,start:Int,end:Int,t:Array[T]):Boolean = {
if (start > end) return false
val pos = (start + end ) / 2
if(t(pos)==x)         true
else if (t(pos) < x)  binSearch(x,pos+1,end,t)
else                binSearch(x,start,pos-1,t)
}

一切都很好，直到我尝试实际使用它(xD):

binSearch(3,0,4,Array(1,2,5,6))

编译器假装 Int 不是 Ord 的成员，但据我所知，类 Int 有 <和>方法。 那么我该怎么做才能解决这个奇怪的问题呢？ 谢谢

Answer 1

最简单的是使用Scala的标准库Ordered[T]特征及其伴随的隐式实例。

通过使用 View 绑定(bind) <% Ordered[T] ，Scala 将寻找隐式 Ordered[T]范围内的实例，并允许您在泛型类型上使用其任何方法(例如 < 、 > 、 >= 、 <= 、 compare )。

这是一个稍微重写的二分搜索函数，

def binarySearch[T <% Ordered[T]](x: T, xs: Seq[T]): Int = {

  def searchBetween(start: Int, end: Int): Int = {
    if (start > end) return -1 // not found

    val pos = (start + end ) / 2

    if (xs(pos) == x) pos // found, return position
    else if (xs(pos) < x) searchBetween(pos+1, end)
    else searchBetween(start, pos-1)
  }

  searchBetween(0, xs.length)
}

然后您可以立即将它与许多常见的类一起使用，例如 Byte , Short , Int , Long , String , BigInt , ... 基本上是 Scala 定义 Ordering[T] 的任何类型实例，或者甚至通过实现 Ordering[YourType] 来提供您自己的实例并将其显式传递给 binarySearch()或在范围内提供隐式实例。

以下是 Int 的示例的和String的:

scala> binarySearch(2, Seq(1,2,3,4,5))                               
res1: Int = 1

scala> binarySearch("d", Seq("a","b","d","f"))   
res2: Int = 2