使用 scala.collection.Searching 时的排序

Question

我有一个[Long， Q]的数组，想对它进行二分搜索。我在下面尝试：

import scala.collection.Searching._
class Q (val b:Double, val a:Double)
val myArray = Array(5L -> new Q(1,2), 6L-> new Q(6,9), 7L-> new Q(7,6))
val i = myArray.search(6L).insertionPoint  

但是有这个错误
没有为任何
定义隐式排序未指定的值参数 ord。
我知道我需要为此集合 Array[(Long，Q(] 指定一个规则，但自己无法弄清楚。
请帮忙

Answer 1

search的签名是search[B >: A](elem: B)(implicit ord: Ordering[B]) 。您有一个类型 [Long, Q] 的数组。因此，为了让编译器正确推断Ordering，您必须像这样调用搜索：

myArray.search(6L-> q/*Q(6,9)*/)(Ordering.by(_._1)) //ordering by the first value in a tuple.

而你正在做的是：myArray.search(6L).如果我正确理解您要做什么，那么可能是在数组中找到值和位置。您可以使用两个单独的数据结构来解决它：

• 密钥可以存储在数组中，如下所示：

  val myArray = Array(5L, 6L, 7L).toList 
  myArray.search(6L).insertionPoint  
  

• 如果你需要值，你可以使用map，它可以用作字典：

  val dictionary = Map(
     5L -> new Q(1,2),
     6L-> new Q(6,9),
     7L-> new Q(7,6)
  )
  

编辑：

实际上，我注意到这样的事情会起作用：

val dummy = new Q(0,0) //any instance of Q
myArray.search(6L-> dummy)(Ordering.by(_._1)).insertionPoint //1

它之所以有效，是因为用于查找插入点Ordering并且不执行相等性测试。