Needle and haystack While Kotlin already provides a binary search implementation for lists, it’s always fun to occasionally implement it yourself just for learning purposes.

In this blog post we will cover these features of Kotlin:

  • Tail recursive functions and the tailrec keyword
  • Extension functions
  • Local functions
  • Generic functions

In case you are not (completely) familiar with the binary search algorithm:

  1. Given an ordered (sorted) list of elements,
  2. Take the element in the middle of the list
  3. Is the element smaller than the “thing” we are tring to find,
  4. Then we can limit our search to the first part of the list
  5. Else we can limit our search to the second part of the list
  6. Repeat until element is found.

Let’s start.

A simple (but naive) implementation could start out like this:

fun binarySearch(list: List<Int>, e: Int): Int {
  // TODO
}

fun main(args: Array<String>) {
  val list = listOf(1, 2, 4, 7, 9, 13, 35, 46, 84, 101, 187, 210)
  println("result: " + binarySearch(list, 101))
}

We can implement the binarySearch function imperatively using a loop or recursively. In this example we’ll pick the recursive implementation, but it needs a helper function. The end result could look similar to this:

fun binarySearch(list: List<Int>, e: Int): Int {
  fun go(low: Int, high: Int): Int {
    val mid = (low + high) / 2
    return if (low == mid) -1 else when (this[mid]) {
      e -> mid
      else -> if (e < this[mid]) go(low, mid) else go(mid, high)
    }
  }
  return go(0, list.size)
}

Tail recursion optimization

This will definitely work for the small list that we are using in the example. But what happens when we want to search a very large list? If the program was written in Java, it would exit with the following error:

Exception in thread "main" java.lang.StackOverflowError

This is because on every recursive call, a new frame is created on the stack which is limited in size and will eventually overflow if there are many recursive calls needed.

Luckily the Kotlin compiler can compile this function to a iterative loop instead because the function is tail recursive. That means the function returns with the last statement being the recursive call. Tail recursive functions can be compiled to iterative loops. To make it clear that this is your intention, you can use the tailrec keyword on the function declaration. Then the compiler will warn you if the function is in fact not tail recursive.

Generic function

Unfortunately our implementation will only work for Int lists. Wouldn’t it be nice to also be able to use this to search other types of lists?

We can make our function generic by replacing Int with a generic type parameter E:

fun <E> binarySearch(list: List<E>, e: E): Int {
  // ...
}

However now the compiler complains that it does not know how to compare elements in the list. We can solve that by specifying that the type that is substituted for E must be a Comparable:

fun <E : Comparable<E>> binarySearch(list: List<E>, e: E): Int {
  // ...
}

Now everything compiles again and it works for any Comparable type including Int.

Extension function

Finally we can improve this by making it an extension function on List and therefore eliminating the need to pass the list as a parameter.

Our program eventually looks like this:

fun <E : Comparable<E>> List<E>.binarySearch(e: E): Int {
  tailrec fun go(low: Int, high: Int): Int {
    val mid = (low + high) / 2
    return if (low == mid) -1 else when (this[mid]) {
      e -> mid
      else -> if (e < this[mid]) go(low, mid) else go(mid, high)
    }
  }
  return go(0, this.size)
}

fun main(args: Array<String>) {
  val list = listOf(1, 2, 4, 7, 9, 13, 35, 46, 84, 101, 187, 210)
  println("result: " + list.binarySearch(101))
}