Binary search library algorithm

Question
1

I found myself writing something like this recently:

import java.util.Collections as JavaCollections
import scala.jdk.CollectionConverters.*

extension [Element](indexedElements: IndexedSeq[Element])
  def indexOf(element: Element)(using ordering: Ordering[Element]): Int =
    val result = JavaCollections.binarySearch(
      indexedElements.asJava,
      element,
      ordering
    )

    // After the fact precondition, the element is expected to be present.
    require(0 <= result)

    result
  end indexOf
end extension

That’s fine in itself, but is there some Scala library equivalent somewhere that does it out of the box?

EDIT: to provide some context, I use random access to the elements in the vast majority of cases, but the elements also have a natural ordering that is consistent by construction with the insertion order; this supports the occasional lookup.

So while a sorted set gives me the desired lookup capability, the API doesn’t support random access (as opposed to an index-augmented RB tree, say).

2

Please see the search method. If called on an indexed seq it performs a binary search (otherwise a linear one).

5 Likes
3

Thanks, @odd - that’s perfect.

I was surprised I hadn’t seen this before - then noticed it was introduced in Scala 2.13. When I dug into this, I found the old Searching syntax enhancement, got a sense of deja-vu and realised I’d been using that several years ago. :man_facepalming:

1 Like