Binary search on an indexed collection (sorted, indexed sequence)

Question

I have an indexed collection (it must be indexed) of some type A :

 var coll: IndexedSeq[A] 

I want to keep coll sorted according to some Ordering[A] , but I often add / remove elements to / from it. The obvious mechanism for this is something like:

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

But there is no binarySearch in the standard library (odd, seeing that there is scala.util.Sorting.quickSort ), and there is no data type that I can find that is indexed and sorted (I assume this is an inefficient structure).

Answer 1

I think slice on TreeSet quite efficient (and you can use it with a singleton range), but you are right - it is strange that there is no indexed sorted data structure. And it is quite effective; most of any sorted tree can be used this way if the number of children is tracked. I think this is just an oversight that it is missing.

You can always use a set for repeating elements if you wrap them with a tag that allows only reference equality, and you can make sure that they are ordered:

 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' 

This adds a lot of overhead for a relatively simple task.

Answer 2

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

Search within an interval in a sorted sequence for a specific item. If the sequence is IndexedSeq, a binary search is used. Otherwise, a linear search is used.

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 

}