Binary Search in Scala

Scala is a programming language that supports both object-oriented as well as functional programming paradigms. Many of the common tasks can be implemented in different ways in Scala and it becomes a matter of style which approach to choose. In this post, I picked one of the classic algorithms, Binary Search, showing how to implement in different ways in Scala. The code is showing 3 functions for binary search: an iterative, recursive, and the functional programming, pattern matching, approach Scala is popular for.

In addition to the difference in style, I was also curious if there are performance differences between these implementations. So, I ran a small experiment, generating a list of 1 billion items, and searching the list 1 million times (each time a different random item is searched) using each of the 3 functions. The results were close, around 1 second total in each of the 3 cases. So, unless different results are observed, I am assuming all approaches are equivalent performance-wise and it's a matter of style and preference which one to use.

It worth mentioning, that I ran the same experiment using java.util.Arrays.binarySearch and the result was also similar.