Question

How to search insert position of K in a sorted list with Scala

Answer 1

// Given a sorted array/vector/list of distinct integers and a target value K, 
// return the index if the target is found. 
// If not, return the index where it would be if it were inserted in order.
 
import scala.util.boundary
import scala.util.boundary.break
 
object SearchInsertPosition {
  def searchInsertPositionOfK(lst: List[Int], k: Int): Int = boundary {
    for (i <- lst.indices) {
      if (lst(i) >= k) {
        break(i)  // Exit the boundary safely
      }
    }
    lst.length
  }
 
 
  def main(args: Array[String]): Unit = {
    val list1 = List(1, 3, 5, 6, 7, 8)
    val k1 = 5
    println(searchInsertPositionOfK(list1, k1))
 
    val list2 = List(1, 3, 5, 6, 7, 8)
    val k2 = 2
    println(searchInsertPositionOfK(list2, k2))
 
    val list3 = List(1, 3, 5, 6, 7, 8)
    val k3 = 9
    println(searchInsertPositionOfK(list3, k3))
  }
}
 
 
 
/*
run:
    
2
1
6
  
*/

 

Learn SQL from A to Z at LearnSQL.com

Answer 2

// Given a sorted array/vector/list of distinct integers and a target value K, 
// return the index if the target is found. 
// If not, return the index where it would be if it were inserted in order.
 
import scala.util.boundary
import scala.util.boundary.break
 
object SearchInsertPosition {
  // Function to find the index of k or the position where it should be inserted - Using Binary Search
  def searchInsertPositionOfK(lst: List[Int], k: Int): Int = boundary {
    var left = 0
    var right = lst.length - 1
 
    while (left <= right) {
      val mid = left + (right - left) / 2
 
      if (lst(mid) == k) {
        break(mid) // Exiting safely using `boundary.break`
      } else if (lst(mid) > k) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }
 
    left
  }
 
  def main(args: Array[String]): Unit = {
    val list1 = List(1, 3, 5, 6, 7, 8)
    val k1 = 5
    println(searchInsertPositionOfK(list1, k1))
 
    val list2 = List(1, 3, 5, 6, 7, 8)
    val k2 = 2
    println(searchInsertPositionOfK(list2, k2))
 
    val list3 = List(1, 3, 5, 6, 7, 8)
    val k3 = 9
    println(searchInsertPositionOfK(list3, k3))
  }
}
 
 
 
/*
run:
    
2
1
6
  
*/

 

Learn SQL from A to Z at LearnSQL.com