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.

	def binarySearchIterative(list: Array[Int], target: Int): Int = {
	var left = 0
	var right = list.length-1
	while (left<=right) {
	val mid = left + (right-left)/2
	if (list(mid)==target)
	return mid
	else if (list(mid)>target)
	right = mid-1
	else
	left = mid+1
	}
	-1
	}
	def binarySearchRecursive(list: Array[Int], target: Int)
	(start: Int=0, end: Int=list.length-1): Int = {
	if (start>end) return -1
	val mid = start + (end-start+1)/2
	if (list(mid)==target)
	return mid
	else if (list(mid)>target)
	return binarySearchRecursive(list, target)(start, mid-1)
	else
	return binarySearchRecursive(list, target)(mid+1, end)
	}
	def binarySearchFunctional(list: Array[Int], target: Int): Int = {
	def bsf(list: Array[Int], target: Int, start: Int, end: Int): Int = {
	if (start>end) return -1
	val mid = start + (end-start+1)/2
	list match {
	case (arr:Array[Int]) if (arr(mid)==target) => mid
	case (arr:Array[Int]) if (arr(mid)>target) => bsf(list, target, start, mid-1)
	case (arr:Array[Int]) if (arr(mid)<target) => bsf(list, target, mid+1, end)
	}
	}
	bsf(list, target, 0, list.length-1)
	}

view raw BinarySearch.scala hosted with ❤ by GitHub

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.