Binary Search for Scala Collections

Binary search is efficient in locating an element or insertion position in a sorted collection. Many programming languages implement binary search for collections in their standard library. Scala is no exception.

Scala provides a unified search method for all sorted collections. Binary search is used for IndexedSeq, e.g. Vector. For LinearSeq (e.g. List), the fallback is linear search.

@ import scala.collection.Searching._ // No longer needed since Scala 2.13.0

@ Vector(1, 3, 5, 7, 9, 11).search(7)
res1: SearchResult = Found(3)

@ Vector(1, 3, 5, 7, 9, 11).search(4)
res2: SearchResult = InsertionPoint(2)

Search can optionally be scoped to part of the collection.

@ Vector(1, 3, 5, 7, 9, 11).search(7)
res1: SearchResult = Found(3)

@ Vector(1, 3, 5, 7, 9, 11).search(7, from = 4, to = 6)
res2: SearchResult = InsertionPoint(4)

Note that it is the caller’s responsibility to ensure the collection to be sorted. Calling search on unsorted collections leads to undefined results.