Scala replacement for Arrays.binarySearch?

Question

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?

Solution 1

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.

Solution 2

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)

Solution 3

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

Comments

[soc]

What about def indexOf (elem: A, from: Int) : Int shouldn't this behave like binarySearch (although possibly slower?)

[Daniel C. Sobral]

@soc Not with that signature, as 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).

[Lambda Fairy]

If binarySearch depends on the items being Comparable, shouldn't we add a constraint such as T <: Comparable[T]?

[piotr]

accessing java List by index can be very inefficient

[hohonuuli]

@piotr. That depends on what's backing a list. For example, an ArrayList is backed by an Array; they both provide similar performance in terms of getting an element by index.

[Matzz]

Unfortunately this solution is suboptimal. 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/…)

[hohonuuli]

Good catch. I hadn't realized that. It looks like scala added scala.collection.Searching in 2.11. So instead you could use: import scala.collection.Searching._; Array(1, 2, 3, 4, 5).search(3)

[samy]

How can i tell the search method that my array is sorted and it can use binary search?

[Joe Pallas]

@samy Your collection must be sorted to use search. That is, if you invoke search on a sequence that is not sorted, the results are undefined.

[samy]

thanks for the explanation but the it seems the method uses linear search on my array of type Array[String] it is magnitudes slower than java.util.Arrays.binarySearch()

[Joe Pallas]

I've not tested the implementation, but I'd be very surprised if it doesn't work as advertised. You might want to post a new question with details of what you've tested and results you've seen.

[samy]

Seems to be a bug in scala 2.11 which was the version i was using, issues.scala-lang.org/browse/SI-9605

[Abhijit Sarkar]

Note that the behavior is different from Java Collections.binarySearch (or Arrays.binarySearch) when the element is not present in the collection. Java returns -1 -insertionPoint, while Scala returns an index > 0. Thus, searching for 3 in [1, 2, 4, 5] would return -3 in Java and 2 in Scala. I personally prefer the Java return value because I can differentiate between the element being present vs absent in the list.

[Joe Pallas]

@AbhijitSarkar You can easily differentiate these cases with the Scala Searching API because the 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.

[Abhijit Sarkar]

@JoePallas You're right, although explicitly returning an Either type would have been better IMO. Also, it's not documented which one is returned if there's a match among duplicates. After looking at the source code, it seems to be arbitrary.

[VaidAbhishek]

You are a savior!