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って遅かったような気もする