CODEWITHSUNDEEP
scala
bsky
bsky

Reputation: 20232

Scala insert element into sorted array in log(N)

I have a sorted Array and I would like to insert a new element in logarithmic time.

I want to do something like this:

def addElem(Array[Int] data, Int x) {
            val pos = java.util.Arrays.binarySearch(data,x);
            data.insertAfter(pos, x);
}

Can I do this with an Array?

Should I try a different data structure?

Upvotes: 0

Views: 1425

Answers (1)

vvg
vvg

Reputation: 6385

Please consider scala collections performance charasteristics:

http://docs.scala-lang.org/overviews/collections/performance-characteristics.html

There are two types of collections that provide Log complexity for insert operation. They are: TreeSet, TreeMap (mutable and immutable).

I would suggest use them.

Regarding Arrays.binarySearch usage. It will not work as most likely you array will not contains x element, so it returns -1. Definitely you can implement binarySearch on Array[Int] by yourself that satisfy your needs.

Upvotes: 2

Related Questions