Is there a replacement in Scala for Java's int Arrays.binarySearch(Object[] array, object)?
The problem is that Scala's Arrays are not covariant, so I would have to cast my stringArray: Array[String] like this first:
stringArray.asInstanceOf[Array[Object]]
Is there a better solution?
Scala 2.11 added scala.collection.Searching to the standard library. It uses binary search for indexed sequences and linear search otherwise.
import scala.collection.Searching._
Array(1, 2, 3, 4, 5).search(3)
search. That is, if you invoke search on a sequence that is not sorted, the results are undefined.SearchResult returned is either a Found or an InsertionPoint. Use a match to tell which case it is, and the two cases will be explicit for anyone reading the code.There isn't anything built in as far as I know, but you can use the pimp-my-library pattern to accomplish this fairly easily. Like so:
class ObjectArrayTools[T <: AnyRef](a: Array[T]) {
def binarySearch(key: T) = {
java.util.Arrays.binarySearch(a.asInstanceOf[Array[AnyRef]],key)
}
}
implicit def anyrefarray_tools[T <: AnyRef](a: Array[T]) = new ObjectArrayTools(a)
scala> Array("a","fish","is","some","thing").binarySearch("some")
res26: Int = 3
scala> Array("a","fish","is","some","thing").binarySearch("bye")
res28: Int = -2
You can add the other java.util.Arrays object methods into the same class if you need them too.
In general, I find it a good idea to get used to always importing a collection of your favorite Scala utilities. It's so easy to add functionality like this that you may as well do it in general rather than keep typing .asInstanceOf[Array[AnyRef]], and with a little effort you can make yourself significantly more productive.
def indexOf (elem: A, from: Int) : Int shouldn't this behave like binarySearch (although possibly slower?)
binarySearch depends on keys being Comparable. IIRC, Java just casts and returns a run-time error, which isn't the kind of thing we want out of Scala. Furthermore, it only works on collections which are ordered, which, again, can't be statically enforced at the moment without an explosion in number of classes (there have been ideas).
binarySearch depends on the items being Comparable, shouldn't we add a constraint such as T <: Comparable[T]?Arrays are funny beasts. If you try the code in the example provided with 'ObjectArrayTools' with this:
Array(1, 2, 3, 4, 5).binarySearch(3)
You get
error: value binarySearch is not a member of Array[Int]
Array(1, 2, 3, 4, 5).binarySearch(3)
For what's going on with Arrays in Scala refer to this document. In any case, you could use this code instead, although it uses Seq instead of Array. However, it has the added bonus of using an Ordering (which just so happens to also be a Java Comparator. So you can customize the ordered behavior if needed.)
import _root_.scala.collection.JavaConversions._
import java.util.{Collections, List => JList}
class SearchableSeq[T](a: Seq[T])(implicit ordering: Ordering[T]) {
val list: JList[T] = a.toList
def binarySearch(key: T): Int = Collections.binarySearch(list, key, ordering)
}
implicit def seqToSearchable[T](a: Seq[T])(implicit ordering: Ordering[T]) =
new SearchableSeq(a)(ordering)
Some examples:
scala> List(1, 2, 3, 4, 5).binarySearch(3)
res0: Int = 2
scala> List(1D, 2D, 3D, 4D, 5D).binarySearch(3.5)
res1: Int = -4
scala> List("a","fish","is","some","thing").binarySearch("bye")
res2: Int = -2
Collections.binarySearch checks if provided list implements RandomAccess interface ("If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons."). None of lists provided by JavaConverters implements that interface. (docs.oracle.com/javase/7/docs/api/java/util/…)scala.collection.Searching in 2.11. So instead you could use: import scala.collection.Searching._; Array(1, 2, 3, 4, 5).search(3)It not that hard to just write it in scala
object BSearch {
def interative[T](array: Array[T], value: T)(implicit arithmetic: Numeric[T]): Int = {
var left: Int = 0;
var right: Int = array.length - 1;
while (right > left) {
val mid = left + (right - left) / 2
val comp = arithmetic.compare(array(mid), value)
if (comp == 0)
return mid; //negative if test < value
else if (comp > 0) //list(mid) > value
right = mid - 1;
else if (comp < 0) //list(mid) < value
left = mid + 1;
}
-1;
}
BSearch.interative(array, value)
Been some years since this question was raised, thought to make some comparison test, hopefully it can help some to decide:
import scala.collection.Searching._
import _root_.scala.collection.JavaConversions._
import java.util.{Collections, List => JList}
import scala.reflect.ClassTag
class ObjectArrayTools[T <: Int](a: Array[T]) {
def binarySearch(key: T) = {
java.util.Arrays.binarySearch(a.asInstanceOf[Array[Int]],key)
}
}
class SearchableSeq[T](a: Seq[T])(implicit ordering: Ordering[T]) {
val list: JList[T] = a.toList
def binarySearch2(key: T): Int = Collections.binarySearch(list, key, ordering)
}
object BinarySearch {
implicit def anyrefarray_tools[T <: Int](a: Array[T]) = new ObjectArrayTools(a)
implicit def seqToSearchable[T](a: Seq[T])(implicit ordering: Ordering[T]) =
new SearchableSeq(a)(ordering)
def main(args:Array[String]) {
val informationArray = Array(1,2,3,4,5,6,7,8,9,10,11,12,14,15,18,20,22,23,25,26)
val informationList = List(1,2,3,4,5,6,7,8,9,10,11,12,14,15,18,20,22,23,25,26)
//val sortedArray = sortList(informationArray)
val sortedArray = informationArray
val sortedList = informationList
for(x <- 0 to 2) {
val startTime = System.nanoTime
val result = binarySearch(sortedArray, 5)
val result2 = binarySearch(sortedArray, 19)
println(s"Custom search time elapsed: ${(System.nanoTime - startTime)}")
val startTime2 = System.nanoTime
val result3 = sortedArray.search(5)
val result4 = sortedArray.search(19)
println(s"Scala search time elapsed: ${(System.nanoTime - startTime2)}")
val startTime3 = System.nanoTime
val result5 = sortedArray.binarySearch(5)
val result6 = sortedArray.binarySearch(19)
println(s"Java search casting time elapsed: ${(System.nanoTime - startTime3)}")
val startTime4 = System.nanoTime
val result7 = sortedList.binarySearch2(5)
val result8 = sortedList.binarySearch2(19)
println(s"Java search as list time elapsed: ${(System.nanoTime - startTime4)}")
val startTime9 = System.nanoTime
val result10 = binarySearchWithImplicitConversion(sortedArray, 5)
val result11 = binarySearchWithImplicitConversion(sortedArray, 19)
println(s"Custom generic time elapsed: ${(System.nanoTime - startTime9)}")
println("---")
}
}
/*def sortList(list:Array[Int]):Array[Int] = {
import com.walcron.etc.Quicksort._
quickSort(list)
}*/
//def binarySearch[T <% Ordered[T]](list:Array[T], valueToBeSearch:T)(implicit t:ClassTag[T]):Int = {
def binarySearch(list:Array[Int], valueToBeSearch:Int):Int = {
def search(start:Int, end:Int):Int = {
val pos = ((end - start) / 2) + start
val curr = list(pos)
if(curr == valueToBeSearch) {
pos
}
else if((end - start) <= 1) {
-1 * (pos + 1) // Indicates the value should be inserted
}
else if(valueToBeSearch > curr) {
search(pos, end)
}
else {
search(start, pos)
}
}
search(0, list.length)
}
def binarySearchWithImplicitConversion[T <% Ordered[T]](list:Array[T], valueToBeSearch:T)(implicit t:ClassTag[T]):Int = {
def search(start:Int, end:Int):Int = {
val pos = ((end - start) / 2) + start
val curr = list(pos)
if(curr == valueToBeSearch) {
pos
}
else if((end - start) <= 1) {
-1 * (pos + 1) // Indicates the value should be inserted
}
else if(valueToBeSearch > curr) {
search(pos, end)
}
else {
search(start, pos)
}
}
search(0, list.length)
}
}
The returned result after 3 runs (as Scala compiler really do need some boost)
Custom search time elapsed: 873373
Scala search time elapsed: 9322723
Java search casting time elapsed: 126380
Java search as list time elapsed: 7375826
Custom generic time elapsed: 4421972
---
Custom search time elapsed: 10372
Scala search time elapsed: 34885
Java search casting time elapsed: 10861
Java search as list time elapsed: 104596
Custom generic time elapsed: 57964
---
Custom search time elapsed: 9121
Scala search time elapsed: 31667
Java search casting time elapsed: 11815
Java search as list time elapsed: 53387
Custom generic time elapsed: 60773
In general, java binary search performed way better; while scala's search did pretty bad. There was also another noticeable performance, it seems that generic typing implicitly drags the performance here badly(so maybe someone can help fix the generic type)...but indirectly it shows a big performance impact.
@moshe-beeri
If you were going to write it in Scala, why would you write it in Java in Scala? Why not actually write it in Scala?
def split(list:List[Char]): (List[Char], List[Char]) = {
val len = list.size
(list.slice(0, len/2), list.slice(len/2,len))
}
def search(target: Char, list: List[Char]):Boolean = {
list match {
case Nil => false
case head :: Nil => if (head == target) true else false
case _ => {
val c = split(list)
if (c._1.last >= target) search(target, c._1) else search(target, c._2)
}
}
}
