Question

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

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.

fun searchInsertPositionOfK(lst: List<Int>, k: Int): Int {
    for (i in lst.indices) {
        // If k is found or needs to be inserted before lst[i]
        if (lst[i] >= k) {
            return i
        }
    }
    // If k is greater than all elements, it should be inserted at the end
    return lst.size
}

fun main() {
    val list1 = listOf(1, 3, 5, 6, 7, 8)
    val k1 = 5
    println(searchInsertPositionOfK(list1, k1))

    val list2 = listOf(1, 3, 5, 6, 7, 8)
    val k2 = 2
    println(searchInsertPositionOfK(list2, k2))

    val list3 = listOf(1, 3, 5, 6, 7, 8)
    val k3 = 9
    println(searchInsertPositionOfK(list3, k3))
}

   
      
/*
run:

2
1
6
  
*/

 

70+ SQL courses for beginners and professionals

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.

// Function to find the index of k or the position where it should be inserted - Using Binary Search
fun searchInsertPositionOfK(lst: List<Int>, k: Int): Int {
    var left = 0
    var right = lst.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2

        when {
            lst[mid] == k -> return mid
            lst[mid] > k -> right = mid - 1
            else -> left = mid + 1
        }
    }

    return left
}

fun main() {
    val list1 = listOf(1, 3, 5, 6, 7, 8)
    val k1 = 5
    println(searchInsertPositionOfK(list1, k1))

    val list2 = listOf(1, 3, 5, 6, 7, 8)
    val k2 = 2
    println(searchInsertPositionOfK(list2, k2))

    val list3 = listOf(1, 3, 5, 6, 7, 8)
    val k3 = 9
    println(searchInsertPositionOfK(list3, k3))
}

   
      
/*
run:

2
1
6
  
*/

 

70+ SQL courses for beginners and professionals