Median of a Array in Kotlin

To find the median of an array, we first need to sort the array in ascending or descending order, depending on whether the array has an even or odd number of elements.

If the array has an odd number of elements, then the median is simply the middle element of the sorted array. If the array has an even number of elements, then the median is the average of the two middle elements of the sorted array.

Here is a sample Kotlin code to find the median of an array:

fun findMedian(array: IntArray): Double {
    val sortedArray = array.sorted()

    return if (sortedArray.size % 2 == 0) {
        // Array has even number of elements
        val midIndex1 = (sortedArray.size / 2) - 1
        val midIndex2 = sortedArray.size / 2
        (sortedArray[midIndex1] + sortedArray[midIndex2]) / 2.0
    } else {
        // Array has odd number of elements
        val midIndex = sortedArray.size / 2
        sortedArray[midIndex].toDouble()
    }
}
fun main() {
    val array = intArrayOf(2, 5, 1, 7, 3, 9, 4, 6, 8)
    val median = findMedian(array)

    println("Median of array: $median")
}

Here’s how the above code works:

1. We begin by sorting the input array using the sorted() method, which returns a new sorted array.
2. Next, we check if the sorted array has an even number of elements by checking if its size is divisible by 2 with a zero remainder.
3. If the sorted array has an even number of elements, we compute the two middle indices midIndex1 and midIndex2. These correspond to the two elements on either side of the middle of the array.
4. We then compute the average of the two middle elements using the formula (sortedArray[midIndex1] + sortedArray[midIndex2]) / 2.0, and return the result.
5. If the sorted array has an odd number of elements, we compute the middle index midIndex using the formula sortedArray.size / 2.
6. We then return the element at the middle index of the sorted array, which is the median.

The time complexity of the findMedian function is O(n log n), where n is the length of the input array. This is because the function first sorts the input array using the sorted() method, which has a worst-case time complexity of O(n log n) for an array of length n.

The space complexity of the function is O(n), where n is the length of the input array. This is because the sorted() method creates a new sorted array of the same length as the input array, and we also use constant space to store the loop index variables and the computed median value, which do not contribute to the space complexity.