ScalaでbinarySearch

標準ライブラリとGoogle先生をざっと眺めた限りScalaの標準コレクションに無さそうだったので。
もし見つかったら更新します。

ここではJavaのjava.util.Collections#binarySearchを使うことを考えます。

def toJavaList[T](arr: Seq[T]): java.util.List[T] = {
  val list = new java.util.ArrayList[T](arr.length)
  arr.foreach{ list.add _ }
  list
}

次にソートと比較用のjava.util.Comparatorを作ります。
リファレンスを見る限りRichIntとかだとjava.lang.Comparableを実装しているっぽいのですが、どうにもうまく動かせなかったので。

// Int用
val cmp = new java.util.Comparator[Int](){ 
  def compare(a: Int, b: Int) = if(a > b) 1 else if(a == b) 0 else -1 
}

後はsortとbinarySearchを呼び出すだけです。
ただ、java.util.Collections.sortは結果を返してくれるわけではないので、toJavaListの呼び出し時にscalaのListでsortをかけて置くと楽です。
個人的には探索(seq.existsなど)の高速化に使用したかったので、そう言った場合の使用例は以下の通りになります。

val list = for(i <- 1 to 10) yield (java.lang.Math.random * 100).toInt
val jlist = toJavaList(list.toList.sort(_<_))
(1 to 100).filter{ n => 
  java.util.Collections.binarySearch(jlist, n, cmp) >= 0 
}

はい、面倒くさいですね。
ただ、単純にexistsを使うだけよりは早いはずです。どうしようもない場合にはどうぞ。

これ使ってみて思ったけれど、Javaのコレクションとscalaコレクションの互換性のなさも結構痛い……
for(i <- jlist) ... みたいにできないみたいだし。
まあ、Javaのコレクションは出来る限り切り捨てたいところではあるんだけれど、こういったAPIを使う場合には使わざるを得ないしなあ。うーん……

追記

id:kmizushimaさんよりコメントにて、scalaのJavaConversionsを使うと上記のコレクションの問題は解決できることを教えていただきました。ありがとうございます。