This is a benchmark that proves thesis: "there is no advantages of using binary search on linked list".

BSonLLBenchmark.scala

object BSonLLBenchmark extends App {

  class HeavyObject(val n: Int) extends Ordered[HeavyObject] {
    def compare(that: HeavyObject): Int = {

      var d = 0
      for (i <- 1 to 100000000) {
        d += (math.abs(math.max(this.n, that.n) / math.min(this.n, that.n)) + 1) / i
      }

      if (this.n < that.n) -d
      else if (this.n > that.n) d
      else 0
    }

    override def equals(o: Any): Boolean =
      o.isInstanceOf[HeavyObject] && compare(o.asInstanceOf[HeavyObject]) == 0

    override def toString: String = "[" + n + "]"
  }

  import scala.util.Random

  def binarysearch[A <% Ordered[A]](list: List[A], key: A): A = {
    def loop(l: List[A], r: List[A]): A =
      if (l == r) null.asInstanceOf[A]
      else test(l, r, middle(l, r))

    def test(l: List[A], r: List[A], m: List[A]): A =
      if (key < m.head) loop(l, m)
      else if (key > m.head) loop(m.tail, r)
      else m.head

    def middle(l: List[A], r: List[A]): List[A] = {
      def race(t: List[A], h: List[A]): List[A] =
        if (h != r && h.tail != r)
          race(t.tail, h.tail.tail)
        else t

      race(l, l.tail)
    }

    loop(list, Nil)
  }

  def linearsearchCond[A](list: List[A], key: A): A = {
    def loop(as: List[A]): A = 
      if (as.isEmpty) null.asInstanceOf[A]
      else if (as.head == key) as.head
      else loop(as.tail)

    loop(list)
  }

  def linearsearchPM[A](list: List[A], key: A): A = {
    def loop(as: List[A]): A = as match {
      case h :: t =>
        if (h == key) h
        else loop(t)
      case Nil => null.asInstanceOf[A]
    } 

    loop(list)
  }

  def linearsearchIter[A](list: List[A], key: A): A = {
    var that: List[A] = list
    var r: A = null.asInstanceOf[A]

    while (!that.isEmpty && r == null) {
      if (that.head == key) r = that.head
      that = that.tail
    }

    r
  }

  def size = 1000

  def generateLongList: List[Long] = {
    val rnd: Random = new Random
    var r: List[Long] = Nil
    for (i <- 1 to size) r = rnd.nextLong :: r
    r.sorted
  }

  def generateHeavyList: List[HeavyObject] = {
    val rnd: Random = new Random
    var r: List[HeavyObject] = Nil
    for (i <- 1 to size) r = new HeavyObject(rnd.nextInt) :: r
    r.sorted
  }

  def launch[A](s: String, f: (List[A], A) => A, l: List[A], k: A): Unit = {

    // warm up
    for (i <- 1 to 10) {
      val kk = f(l, k)
      println("warming up for: " + kk)
    }

    // steady stage
    val t0 = System.currentTimeMillis()
    val kk = f(l, k)
    val t1 = System.currentTimeMillis()

    // output
    println(s + ": " +  (t1 - t0) + "ms for " + kk)
  }

  def test[A <% Ordered[A]](l: List[A]): Unit = {

    // init
    val r = new Random
    val i = r.nextInt(l.length)
    val k = l(i)

    println("Searching for " + i + " in " + size)

    // launch
    launch("linearsearchCond", linearsearchCond[A], l, k)
    launch("binarysearch", binarysearch[A], l, k)
  }

  //test(generateLongList)
  test(generateHeavyList)
}