2

我正在编写一个通用的二进制搜索实现,我无法编译这个(compare is not a member of type parameter B),即使它B是一个Ordering并且它应该被隐式转换为Ordered具有该compare方法的:

  /**
   * Generic binary search in (min,max) f to achieve target goal
   * O(log n)
   *
   * @param f the function to binary search over - most be monotonically increasing
   * @param min starting minimum guess (must be exclusive)
   * @param max starting maximum guess (must be exclusive)
   * @param avg mid function usually (min+max)/2
   * @param goal target to achieve
   * @tparam A input type of f
   * @tparam B output type of f
   * @return Some(x) such that f(x) is goal else None
   */
  import scala.math.Ordering.Implicits._

  def binarySearch[A: Ordering, B: Ordering](f: A => B, min: A, max: A, avg: (A, A) => A, goal: B): Option[A] = {
    if (min >= max) {
      None
    } else {
      val mid = avg(min, max)
      f(mid) compare goal match {
        case  1 => binarySearch(f, min, mid, avg, goal)
        case -1 => binarySearch(f, mid, max, avg, goal)
        case  0 => Some(mid)
      }
    }
  }
4

1 回答 1

4

尝试导入scala.math.Ordered

import scala.math.Ordered._

它具有类型元素的隐式转换,BOrdered允许在范围内存在Ordering类型的类型类B

于 2013-04-18T07:53:07.960 回答