scala-binary-search-example.md

scala.collection.Searching provides binary search but you need an Indexed sequence (eg. Array), not a Linear sequence (eg. List). Search will still work on the List but you get linear O(n) behaviour rather than O(Log n).

case class Employee (id: Int, name: String, age: Int)

val emp1 = Employee(1, "Jane Doe", 45)
val emp2 = Employee(2, "Jon Doe", 54)
val emp3 = Employee(3, "Tera Patrick", 38)
val emp4 = Employee(4, "Jenna Jameson", 36)
val emp5 = Employee(5, "Aurora Snow", 34)     // not added

val employeeList = List(emp1, emp2, emp3, emp4)

List is a Linear Seq rather than an Indexed Seq so we will convert it to an array.

As an aside, PreDef will implicitly convert our Array to either an ArrayOps or a WrappedArray - both are mutable structures.

val employees = employeeList.toArray

Let's say we wish to search the sequence of Employees by their names. In this case, we need to sort them in lexicographical order of their names. We need to provide an implicit Ordering for this.

import scala.math.Ordering

implicit object NameOrdering extends Ordering[Employee] {
  def compare(a:Employee, b:Employee) = a.name compare b.name
}

Now we can sort employees by their names. The sequence should be sorted with the same Ordering before calling search otherwise the results are undefined.

import scala.util.Sorting

Sorting.quickSort(employees)(NameOrdering)

Now we can search.

import scala.collection.Searching._

If the element is found its index is returned.

scala> val result = employees.search(emp3)
result: collection.Searching.SearchResult = Found(3)

To retrieve the element use the insertionPoint method on the result.

scala> employees(result.insertionPoint)
res6: Employee = Employee(3,Tera Patrick,38)

If the element is not found then the index of its insertion point in the sorted sequence is returned.

scala> employees.search(emp5)
res2: collection.Searching.SearchResult = InsertionPoint(0)

Since we never inserted "Aurora Snow" to the sequence of employees, she is not found. However, we do get the insertion point index which is 0. This is because according to our ordering by name, "Aurora Snow' would be the first Employee in the order and therefore the first element in the sequence, hence index 0 is returned.