Бинарный поиск в индексированной коллекции (отсортированная, индексированная последовательность)

Question

У меня есть проиндексированная коллекция (она должна быть проиндексирована) некоторого типа A:

var coll: IndexedSeq[A]

Я хочу сохранить coll отсортированным в соответствии с некоторыми Ordering[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

Я думаю, slice на TreeSet достаточно эффективен (и вы можете использовать его с диапазоном из одного элемента), но вы правы - странно, что нет индексированной отсортированной структуры данных. И это достаточно эффективно; почти любое отсортированное дерево может быть использовано таким образом, если отслеживается количество детей. Я думаю, что это просто упущение, которого не хватает.

Вы всегда можете использовать набор для повторяющихся элементов, если заключите их в тег, который допускает только равенство ссылок, и убедитесь, что они упорядочены:

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 / апи / 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

}