Why my Binary Search implementation in Scala is so slow?

Question

Recently, I implemented this Binary Search, which is supposed to run under 6 seconds for Scala, yet it runs for 12-13 seconds on the machine that checks the assignments.

Note before you read the code: the input consists of two lines: first - list of numbers to search in, and second - list of "search terms" to search in the list of numbers. Expected output just lists the indexes of each term in the list of numbers. Each input can be maximum of length 10^5 and each number maximum of size 10^9.

For example:

Input:
5 1 5 8 12 13 //note, that the first number 5 indicates the length of the 
following sequence

5 8 1 23 1 11 //note, that the first number 5 indicates the length of the 
following sequence

Output:
2 0 -1 0 -1 // index of each term in the input array

My solution:

object BinarySearch extends App {
  val n_items = readLine().split(" ").map(BigInt(_))
  val n = n_items(0)
  val items = n_items.drop(1)

  val k :: terms = readLine().split(" ").map(BigInt(_)).toList

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

  def search(terms: List[BigInt], items:Array[BigInt]): Array[BigInt] = {
    @tailrec
    def go(terms: List[BigInt], results: Array[BigInt]): Array[BigInt] = terms match {
      case List() => results
      case head :: tail => go(tail, results :+ find(head))
    }

    def find(term: BigInt): BigInt = {
      @tailrec
      def go(left: BigInt, right: BigInt): BigInt = {
        if (left > right) { -1 }
        else {
          val middle = left + (right - left) / 2
          val middle_val = items(middle.toInt)

          middle_val match {
            case m if m == term => middle
            case m if m <= term => go(middle + 1, right)
            case m if m > term => go(left, middle - 1)
          }
        }
      }

      go(0, n - 1)
    }

    go(terms, Array())
  }
}

What makes this code so slow? Thank you

Answer 1

I am worried about the complexity of

results :+ find(head)

Appending an item to a list of length L is O(L) (see here), so if you have n results to compute, the complexity will be O(n*n).

Try using a mutable ArrayBuffer instead of an Array to accumulate the results, or simply mapping the input terms through the find function.

In other words replace

go(terms, Array())

with

terms.map( x => find(x) ).toArray

By the way, the limits on the problem are small enough that using BigInt is overkill and probably making the code significantly slower. Normal ints should be large enough for this problem.