对索引集合（排序的索引序列）进行二分搜索

Question

我有一个A类型的索引集合（必须已索引）：

var coll: IndexedSeq[A]

我希望根据某些排序保持coll排序[A] 但我经常向其中添加/删除项目。执行此操作的明显机制类似于：

def binarySearch[A : Ordering](a: IndexedSeq[A], elem: A): Int
def add(a: A) {
  val idx = binarySearch(coll, a)
  coll = (coll take idx) :+ a +: (coll drop idx)
}

但是标准库中既没有 binarySearch （奇怪，因为有 scala.util.Sorting.quickSort）并且我找不到既可以索引又可以排序的数据类型（我猜这是一个低效的结构）。

Answer 1

我认为 TreeSet 上的 slice 相当有效（并且您可以将它与单元素范围一起使用），但您是对的 - 没有索引很奇怪排序的数据结构。而且效率足够高；如果跟踪子级的数量，则大多数排序树都可以以这种方式使用。我认为这只是一个疏忽，它的缺失。

如果您使用仅允许引用相等的标记包装重复元素，则始终可以对它们使用集合，并且可以确保它们是有序的：

class Tag[A](val value: A)(implicit ord: Ordering[A]) extends Ordered[Tag[A]] {
  def compare(ta: Tag[A]) = {
    val c = ord.compare(value,ta.value)
    if (c != 0) c
    else if (this eq ta) 0
    else System.identityHashCode(this) compare System.identityHashCode(ta)
  }
  override def toString = value.toString+"'"
  override def hashCode = value.hashCode
  override def equals(a: Any) = a.asInstanceOf[AnyRef] eq this
}

scala> collection.immutable.TreeSet[Tag[Int]]() ++ List(1,2,3,2,1).map(i => new Tag(i))
res1: scala.collection.immutable.TreeSet[Tag[Int]] = TreeSet(1', 1', 2', 2', 3')

scala> res1.slice(2,3).head
res2: Tag[Int] = 2'

但是，对于相对简单的任务，这确实会增加大量开销。

Answer 2

http://www.scala-lang.org /api/2.11.4/index.html#scala.collection.Searching$$SearchImpl

在排序序列的某个区间内搜索特定元素。如果序列是 IndexedSeq，则使用二分搜索。否则，将使用线性搜索。

Answer 3

def getPerson(userList: ArrayList[Person], person: Person): Integer = {
var low = 0;
var high = userList.size - 1

while (low <= high) {
  var mid = low + (high - low) / 2
  var midValue = userList.get(mid)
  if (person.firstName < midValue.firstName) {
    high = mid - 1;
  } else if (person.firstName > midValue.firstName) {
    low = mid + 1;
  } else {
    return mid
  }
}
return -1

}