好的，所以我试图在Scala中用二进制搜索来找到给定区间的最小值，但最小值必须与给定函数匹配。这是我的代码：
def binarySearch: (Int => Boolean) => (Int, Int) => Int = f => (l, h) => {
def bs: ((Int => Boolean) => (Int, Int, Int) => Int) = f => (l, h, minimum) => {
val mid = l + ((h-l) / 2)
mid match{
case mid if(f(mid) == false) => bs(f)(mid+1, h, mid)
case mid if(f(mid) == true && mid > minimum) => bs(f)(l, mid-1, minimum)
case mid if(f(mid) == true && mid < minimum) => bs(f)(mid+1, h, mid)
case mid => mid
}
}
bs(f)(l, h, 0)
}
我想我的问题是，我没有正确地保存最低限度。
测试用例可能如下所示：
val v = Vector(0, 1, 2, 3, 7, 9)
binarySearch(v(_) < 5)(0, v.length) == 4
有什么想法吗？
这种声明方法的风格非常不寻常，会使代码难以阅读和理解。因此，我的第一步是以更惯用的、传统的形式复制代码
我采取的步骤如下：
- IMHO，函数最好接受参数，而不是返回接受参数的匿名函数。它更简单、更干净，让你的意图更清晰
- 将谓词函数命名是惯例—那些通常只接受一个参数并返回
Boolean—CCD_ 2 - 在
bs中，其谓词函数自变量的重新声明是多余的；它可以重用提供给binarySearch的谓词，因此不需要重新声明它 - 在测试
Boolean值时，通常让该值保持不变。也就是说，如果boolExpr是值为true或false的Boolean表达式，则应该更喜欢if(boolExpr)而不是if(boolExpr == true)，更喜欢if(!boolExpr)而不是if(boolExpr == false) - 如果前面的情况都不匹配，则可以使用默认情况
case _。这比代码中的case mid要清晰一些
然后您的原始代码变为：
def binarySearch(p: Int => Boolean)(l: Int, h: Int): Int = {
def bs(l: Int, h: Int, minimum: Int): Int = {
val mid = l + ((h - l) / 2)
mid match {
case mid if(!p(mid)) => bs(mid+1, h, mid)
case mid if(p(mid) && mid > minimum) => bs(l, mid-1, minimum)
case mid if(p(mid) && mid < minimum) => bs(mid+1, h, mid)
case _ => mid
}
}
bs(l, h, 0)
}
好的，现在我们来调试您的函数。您声称它应该计算给定区间的最小值，并且的最小值必须与给定函数匹配。或者，换句话说，它应该在满足谓词的范围内找到最小值。
但是，在您的测试用例中，您的谓词是该值必须小于5，并且您期望值4作为答案。
一些问题是显而易见的：
- 您的代码假设但不验证数据是从低到高排序的。我之所以提到这一点，是因为很明显，如果数据不按顺序排列，代码就会失败。如果你能保证这个假设成立，那也没关系
l、h、mid和minimum都是属于从p1不可访问的Vector的值的索引；但它们本身并不是价值观。这与你所说的你在寻找最小值相矛盾；相反，它看起来像是在寻找最小值的索引- 在测试条件下，您期望值4，它是值7的索引。然而，7使谓词失效，因为它不小于5。这让我怀疑您的测试中的谓词函数应该是
binarySearch(v(_) >= 5)(0, v.length) - 您未验证
l是否小于binarySearch中的h，这表明您没有可搜索的范围。如果在bs中发生这种情况，则应将其视为终止条件(已完全搜索范围)，并返回找到的最小值索引。(在现有代码中似乎没有这样的终止条件，因此它可以在某些情况下无限循环，最终产生StackOverflowError。) - 您应该注意，使用谓词函数的二进制搜索从根本上讲是有缺陷的，除非谓词拆分范围，使得所有未通过谓词的值的索引都是连续的，并出现在范围的开头，并且通过谓词的所有值的索引在范围的末尾都是连续。为了说明这一点，考虑一下如果谓词只接受偶数值：
binarySearch(v(_) % 2 == 0)(0, v.length)会发生什么？(提示：您的函数需要访问范围内的每个元素，以确保找到最小值，而二进制搜索不是这样做的。) - 如果您的搜索找不到满足谓词的最小值，那么它就无法表示事实。因此，我认为函数应该返回
Option[Int]，如果找不到值，则返回值None，否则返回Some(minimum) - 如果检查了具有该索引的元素的值，则为
h传递v.length将导致抛出IndexOutOfBoundsException。您应该传递v.length - 1，或者将h视为超出范围末尾的一个位置
更新
为了解决您的实现问题，我对问题进行了轻微的结构调整。现在，binarySearch函数使用二进制搜索来查找大于指定最小值的最低值。为此，它接受一个名为seq的IndexedSeq和一个可以接受的minimum值，而不是一个具有低索引和高索引的谓词函数。
// Return None if no value found, or Some(min index) otherwise.
def binarySearch(seq: IndexedSeq[Int], minimum: Int): Option[Int] = {
// Helper function. Check middle value in range. Note: h is one position beyond end of
// current range.
def bs(l: Int, h: Int, min: Option[Int]): Option[Int] = {
// If the l index isn't less than the h index, then we have nothing more to search for.
// Return whatever our current minimum is.
if(l >= h) min
// Otherwise, find the middle index value of this range.
else {
val mid = l + ((h - l) / 2)
assert(mid >= l && mid < h) // Sanity check.
// Determine if the middle value is large enough.
if(seq(mid) >= minimum) {
// OK. So this value qualifies. Update our minimum. Any potentially lower values are
// going to be in the range below mid, so look there next.
val nextMin = min.filter(_ < mid).orElse(Some(mid))
bs(l, mid, nextMin)
}
// No luck. Search the range above mid with the same minimum.
else bs(mid + 1, h, min)
}
}
// Start the search. Our initial minimum value is None.
bs(0, seq.length, None)
}
以下是Scala REPL:中的一些示例
scala> val v = Vector(0, 1, 2, 3, 7, 9)
v: scala.collection.immutable.Vector[Int] = Vector(0, 1, 2, 3, 7, 9)
scala> binarySearch(v, 5)
res0: Option[Int] = Some(4)
scala> binarySearch(v, 9)
res1: Option[Int] = Some(5)
scala> binarySearch(v, 50)
res2: Option[Int] = None
scala> binarySearch(v, -1)
res3: Option[Int] = Some(0)
我的代码与helper函数有点复杂。。这是一个可能的正确解决方案：
def binarySearch: (Int => Boolean) => (Int, Int) => Int = f => (l, h) => {
val mid = l + ((h-l) / 2)
mid match {
case _ if(l >= h) => h
case mid if(f(mid)) => binarySearch(f)(l,mid)
case mid => binarySearch(f)(mid+1, h)
}
}
不幸的是，我们不得不使用这种风格来声明方法