我正在编写一个通用的二进制搜索实现,我无法编译这个(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)
}
}
}