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

• Voo: 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.
• Random Dev: yes thank you for pointing this out - big blunder there on my part!
• Oliver Joseph Ash: Why use pattern matching on ds(mid) instead of just plain if/else if/else?
• Random Dev: @OliverJosephAsh because you would get two nested ifs which most people see as ugly and in my opinion the match is just more readable