# Binary search in functional-style Scala

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


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

• You introduced a serious bug by changing the code from (high - mid + 1) / 2 + mid to mid = (lo + hi) / 2 - the first one is safe from overflow, the later isn't. The correct code is lo + (hi - lo) / 2.
– Voo
Jun 29, 2014 at 22:28
• yes thank you for pointing this out - big blunder there on my part! Jun 30, 2014 at 4:04
• Why use pattern matching on ds(mid) instead of just plain if/else if/else? Feb 20, 2016 at 18:31
• @OliverJosephAsh because you would get two nested ifs which most people see as ugly and in my opinion the match is just more readable Feb 20, 2016 at 19:27