如何在 Scala 的区间内使用二进制搜索找到最小值？

Question

好吧，我正在尝试在 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

有什么想法吗？

Answer 1

这种声明方法的风格很不寻常，使您的代码难以阅读和理解。因此，我的第一步是以更惯用、更传统的形式重现您的代码。

我采取的步骤如下：

恕我直言，函数接受参数比 return 接受参数的匿名函数更可取。它更简单、更清晰，让您的意图更清晰。
通常命名为 predicate 函数——那些通常采用单个参数并且 return 一个 Boolean—p.
在bs中，其谓词函数参数的重新声明是多余的；它可以重新使用提供给 binarySearch 的谓词，因此不需要重新声明它。
测试 Boolean 值时，通常让值保持不变。也就是说，如果 boolExpr 是具有值 true 或 false 的 Boolean 表达式，您应该更喜欢 if(boolExpr) 而不是 if(boolExpr == true) 和 if(!boolExpr) 到 if(boolExpr == false).
默认情况下，如果 none 前面的情况匹配，则可以使用 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 都是属于 Vector 的值的索引，无法从 binarySearch 访问——但它们本身并不是价值观。这与您正在寻找最小值的说法相矛盾；相反，您似乎在寻找最小值的 index。
在你的测试条件下，你期望值 4，它是值 7 的索引。但是，7 不符合谓词，因为它不小于 5。这让我怀疑你的谓词函数在你的测试应该是 binarySearch(v(_) >= 5)(0, v.length).
您在binarySearch中没有验证l小于h，说明您没有搜索范围。如果在bs中出现这种情况，那么你应该将其视为终止条件（范围已被完全搜索）和return找到的最小值索引。（您现有的代码中似乎没有这样的终止条件，因此它可以在某些情况下无限循环，最终导致 WhosebugError。）
你应该注意到，使用谓词函数的二分搜索从根本上是有缺陷的，除非谓词分割范围使得所有不符合谓词的值的索引都是连续的并出现在范围的开头，并且通过谓词的所有值的索引在范围的末尾是连续的。为了说明这一点，考虑如果谓词只接受偶数值会发生什么：binarySearch(v(_) % 2 == 0)(0, v.length)？（提示：您的函数需要访问范围内的每个元素以保证找到最小值，而这不是二分查找的作用。）
如果您的搜索找不到满足谓词的最小值，则无法表明事实。出于这个原因，我认为如果找不到值，您的函数应该 return Option[Int] 值 None 被 return 编辑，否则 Some(minimum) 。
如果检查具有该索引的元素的值，则将 v.length 传递给 h 将导致抛出 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)

Answer 2

我的代码与辅助函数复杂化了..这是一个可能的正确解决方案：

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)
}

}

不幸的是，我们必须使用这种声明方法的方式

如何在 Scala 的区间内使用二进制搜索找到最小值？

How can I find the minimum with binary search on an interval in Scala?

scala

minimum

binary-search