An unoptimized Scala equivalent of C++'s std::lower_bound and std::upper_bound

BinarySearch.scala

import scala.annotation.tailrec

object BinarySearch {
  def lowerBound(xs: Array[Int], x: Int): Int = {
    @tailrec
    def loop(first: Int, count: Int): Int =
      if (count == 0) first
      else {
        val step = count / 2
        if (xs(first + step) < x) loop(first + step + 1, count - step - 1)
        else loop(first, step)
      }

    loop(0, xs.length)
  }

  def upperBound(xs: Array[Int], x: Int): Int = {
    @tailrec
    def loop(first: Int, count: Int): Int =
      if (count == 0) first
      else {
        val step = count / 2
        if (x < xs(first + step)) loop(first, step)
        else loop(first + step + 1, count - step - 1)
      }

    loop(0, xs.length)
  }
}

BinarySearchSpecification.scala

import org.scalacheck.{Properties, Gen}
import org.scalacheck.Prop.forAll
import scala.annotation.tailrec
import tnoda.binarysearch.BinarySearch._

object BinarySearchSpecification extends Properties("BinarySearch") {
  val SmallInt = 1000
  val genSmallInt = Gen.choose(0, SmallInt)
  val genIntArray = Gen.containerOf[Array, Int](genSmallInt)

  property("lowerBound") = forAll(genIntArray, genSmallInt){ (xs: Array[Int], x: Int) =>
    lowerBound(xs.sorted, x) == xs.count(_ < x)
  } && forAll(genIntArray) { xs =>
    lowerBound(xs.sorted, xs.foldLeft(-1)(_ max _) + 1) == xs.length
  } && forAll(genIntArray) { xs =>
    lowerBound(xs.sorted, 0) == 0
  }

  property("upperBound") = forAll(genIntArray, genSmallInt) { (xs: Array[Int], x: Int) =>
    upperBound(xs.sorted, x) == xs.count(_ <= x)
  } && forAll(genIntArray) { xs =>
    upperBound(xs.sorted, xs.foldLeft(-1)(_ max _) + 1) == xs.length
  } && forAll(genIntArray) { xs =>
    lowerBound(xs.sorted, -1) == 0
  }
}

Not correct