Scala替换Arrays.binarySearch？

Scala中是否有替换Java的int Arrays.binarySearch(Object[] array, object) ？

问题是Scala的数组不是协变的，所以我必须先将我的stringArray: Array[String] ：

 stringArray.asInstanceOf[Array[Object]] 

有更好的解决方案吗？

Answer 1

据我所知，没有内置任何内容，但您可以使用pimp-my-library模式轻松完成此任务。 像这样：

 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 

如果需要，可以将其他java.util.Arrays对象方法添加到同一个类中。

一般来说，我觉得习惯于总是导入你最喜欢的Scala实用程序的集合是一个好主意。 添加这样的function非常容易，你也可以这样做，而不是继续输入.asInstanceOf[Array[AnyRef]] ，只需稍加努力就可以让自己显着提高工作效率。

Answer 2

Scala 2.11添加了scala.collection.Searching到标准库。 它使用二进制搜索索引序列，否则使用线性搜索。

 import scala.collection.Searching._ Array(1, 2, 3, 4, 5).search(3) 

Answer 3

数组是有趣的野兽。 如果您尝试使用’ObjectArrayTools’提供的示例中的代码：

 Array(1, 2, 3, 4, 5).binarySearch(3) 

你得到

 error: value binarySearch is not a member of Array[Int] Array(1, 2, 3, 4, 5).binarySearch(3) 

有关Scala中Arrays的内容，请参阅此文档 。 在任何情况下，您都可以使用此代码，尽管它使用Seq而不是Array。 但是，它还有一个额外的好处，就是使用Ordering（它恰好也是一个Java Comparator。所以你可以根据需要自定义有序行为。）

 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) 

一些例子：

 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 

Answer 4

在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) 

Answer 5

在提出这个问题已经有好几年了，想过做一些比较测试，希望它可以帮助一些人做出决定：

 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) } } 

3次运行后返回的结果（因为Scala编译器确实需要一些提升）

 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 

一般来说，java二进制搜索执行方式更好; 斯卡拉的搜索确实非常糟糕。 还有另一个值得注意的表现，似乎generics类型隐含地拖累了这里的性能（所以也许有人可以帮助修复generics类型）……但是它间接表现出很大的性能影响。

Answer 6

@摩西 – 比里

如果您要在Scala中编写它，为什么要在Scala中用Java编写它？ 为什么不在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) } } }