Binary search in functional-style Scala

Question

Curious to know how I can improve it, especially the pattern matching part seems a bit repetitive at the moment (lots of case x if ds(x))

  def binarySearch(ds: Array[Double], key: Double): Int = {
    @annotation.tailrec
    def go(low: Int, mid: Int, high: Int): Int = {
      mid match {
        case x if ds(x) == key => x
        case x if high <= low => -1
        case x if ds(x) < key => go(mid + 1, (high - mid + 1) / 2  + mid, high)
        case x if ds(x) > key => go(low, (mid - low) / 2 + low, mid - 1)
      }
    }
    ds.size match {
      case 0 => -1
      case _ => go(0, ds.size / 2, ds.size - 1)
    }
  }

Answer 1

the high <= low part does not involve x and could be pulled out of the case. The rest is fine IMHO.

One remark: the -1 return in the error-case is a bit of a smell - why not return Option[Int] instead?

And finally: I think you don't need mid as an argument - as you guard for low > high anyway you can as easily compute it inside your inner function and make the calls a bit more readable (only low and high)

Could look like this

  type Index = Int

  def binarySearch(ds: Array[Double], key: Double): Option[Index] = {
      @tailrec
      def go(lo: Index, hi: Index): Option[Index] = {
        if (lo > hi)
          None
        else {
          val mid: Index = lo + (hi - lo) / 2
          ds(mid) match {
            case mv if (mv == key) => Some(mid)
            case mv if (mv <= key) => go(mid + 1, hi)
            case _ => go(lo, mid - 1)
          }
        }
      }
      go(0, ds.size - 1)
  }