为何我用Scala实现的Binary Search运行速度过慢？

Let's break down the key bottlenecks in your code that are causing the 2x slowdown compared to the time limit:

1. Unnecessary Use of BigInt #

Your input numbers max out at 10^9, which fits comfortably within Scala's Int (max value ~2e9) or Long (for extra headroom). Using BigInt adds significant overhead for every arithmetic operation, array access, and string parsing—this is a major contributor to the slowdown. Every time you do middle.toInt or compare BigInt values, you're paying a cost that native numeric types avoid entirely.

2. Inefficient Result Collection with Array :+ #

The line go(tail, results :+ find(head)) creates a new array every time you append a result. For 10^5 search terms, this results in an O(k²) time complexity (since each copy takes O(n) time). Scala's immutable-style Array operations like :+ are not designed for frequent appends—you should use a mutable ArrayBuffer instead, which provides amortized O(1) append operations.

3. List Conversion for Search Terms #

Converting the search terms array to a List (toList) adds unnecessary overhead. Arrays are more efficient for sequential access and iteration in Scala, especially for large datasets.

Optimized Code Example #

Here's a revised version of your code that addresses all these issues:

import scala.annotation.tailrec
import scala.collection.mutable.ArrayBuffer

object BinarySearch extends App {
  // Read input using native Long type (safe for 1e9 values)
  val inputItems = readLine().split(" ").map(_.toLong)
  val n = inputItems(0).toInt
  val items = inputItems.drop(1)

  val inputTerms = readLine().split(" ").map(_.toLong)
  val terms = inputTerms.drop(1)

  println(search(terms, items).mkString(" "))

  def search(terms: Array[Long], items: Array[Long]): Array[Long] = {
    val results = ArrayBuffer[Long]()
    @tailrec
    def go(terms: Array[Long], idx: Int): Unit = {
      if (idx >= terms.length) ()
      else {
        results += find(terms(idx))
        go(terms, idx + 1)
      }
    }

    def find(term: Long): Long = {
      @tailrec
      def go(left: Int, right: Int): Long = {
        if (left > right) -1L
        else {
          // Use integer arithmetic directly (no BigInt overhead)
          val middle = left + (right - left) / 2
          val middleVal = items(middle)
          if (middleVal == term) middle.toLong
          else if (middleVal < term) go(middle + 1, right)
          else go(left, middle - 1)
        }
      }
      go(0, n - 1)
    }

    go(terms, 0)
    results.toArray
  }
}

Additional Notes #

• We use Long instead of Int just to be safe (though Int would work for 1e9), but the key is avoiding BigInt.
• ArrayBuffer is used to collect results efficiently without repeated array copies.
• The search loop uses array indexing instead of List pattern matching, which is faster for large datasets.
• All arithmetic operations are done with native integer types, eliminating the overhead of arbitrary-precision arithmetic.

These changes should bring your runtime well under the 6-second limit by reducing unnecessary overhead and fixing the O(k²) result collection bottleneck.

内容的提问来源于stack exchange，提问作者Shkarik