Skip to content

Instantly share code, notes, and snippets.

@jrudolph
Created May 29, 2010 07:03
Show Gist options
  • Save jrudolph/418099 to your computer and use it in GitHub Desktop.
Save jrudolph/418099 to your computer and use it in GitHub Desktop.
def binarySearch[B, A <% Ordered[B]](a: Array[A], v: B) = {
def recurse(low: Int, high: Int): Option[Int] = (low + high) / 2 match {
case _ if high < low => None
case mid if a(mid) > v => recurse(low, mid - 1)
case mid if a(mid) < v => recurse(mid + 1, high)
case mid => Some(mid)
}
recurse(0, a.size - 1)
}
case class Thing(val n:Int)
implicit val compThingToThing: Thing => Ordered[Thing] =
t => new Ordered[Thing] {
def compare(that: Thing): Int = { t.n - that.n }
}
implicit val compThingToInt: Thing => Ordered[Int] =
t => new Ordered[Int] {
def compare(that: Int): Int = { t.n - that }
}
val a:Array[Thing] = Array(Thing(1), Thing(3), Thing(5), Thing(6))
binarySearch(a, Thing(5)) // compiles, compThingToThing is available
binarySearch(a, 5) // compiles, compThingToInt is available
binarySearch(a, "test") // doesn't compile, it isn't known how to compare Things to strings
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment