Find last index where an element should be inserted in order to maintain order

user_11013878 0
Viewed 119

I am trying to implement the searchsorted algorithm(side=right) in scala that is, find last index where an element should be inserted in order to maintain the sorting order.

For ex.

val arr = List(1,2,2,3,4,4,6,6). // assume list is sorted, also array can have negetive elements(albeit sorted)
if elem = 2, output index = 3
if elem = 3, output index = 4
if elem = 5, output index = 6
if elem = -3, output index = 0

I came up with this, iterating through each element in the list, and checking the smallest diff

val a = List(1,1,2,2,3,3,4,5,5)
val elem = 1
val (_, index) = a
.foldLeft(Int.MaxValue, 0) {
    case ((smallestDiff, index), currNum) =>
        val currDiff = (elem - currNum).abs
        if (currDiff > smallestDiff) (smallestDiff, index)
        else (currDiff, index + 1)
}

This one works fine for 1st 2 examples, but completely breaks for last 2 ex

scala
1 Answers

indexWhere() can do most of the heavy lifting.

def insertHere(ns:Seq[Int], elem:Int):Int = {
  val idx = ns.indexWhere(_ > elem)
  if (idx < 0) ns.length
  else idx
}
insertHere(  List(1,2,2,3,4,4,6,6), 2) // 3
insertHere(   Seq(1,2,2,3,4,4,6,6), 3) // 4
insertHere( Array(1,2,2,3,4,4,6,6), 5) // 6
insertHere(Vector(1,2,2,3,4,4,6,6),-3) // 0
insertHere(  List(1,2,2,3,4,4,6,6),12) // 8

This returns the non-existing index when elem should be appended at the end.

user_49931280
Related