Scalaで範囲付き二分探索

これは文字列の探索。dankogai氏のblogのjsを見ていじった。

object TryBinarySearch {
  def main(args:Array[String]) {
    var strs = Array[String]("a", "ab", "abc", "abcd", "cc", "dd", "ee") // sort済
    val (found, head, tail)  = binarySearch(strs, "a")
    println(found.toString) // true
    println(head.toString)  // 0
    println(tail.toString)  // 3
  }

  def binarySearch(strs:Array[String], target:String) : (Boolean, Int, Int) = {
    var (lower, upper) = (0, strs.length - 1)
    while (upper >= lower) {
      var i   = lower + (upper - lower) / 2
      if (strs(i).startsWith(target)) {
        val head = linearSearch(strs, target, i, -1)
        val tail = linearSearch(strs, target, i,  1)
        return (true, head, tail)
      }
      if (strs(i) < target) lower = i + 1 else upper = i - 1
    }
    return (true, upper, lower)
  }

  // 見つかった場所を軸に1つずつ見ていく
  def linearSearch(strs:Array[String], target:String, pivot:Int, dir:Int) : Int = {
    val r              = if (dir > 0) true else false
    var (lower, upper) = if (r) (pivot, strs.length - 1) else (0, pivot)
    while (upper >= lower) {
      var i = lower + (upper - lower) / 2
      if (strs(i).startsWith(target) ^ r) upper = i - 1 else lower = i + 1
    }
    if (r) upper else lower
  }
}

XORって遅かったような気もする